Trouver le 2ème plus grand élément dans un tableau avec le nombre minimum de comparaisons

L'algorithme optimal utilise n+log n-2 comparaisons. Pensez à des éléments comme des concurrents, et un tournoi est de les classer.

Tout d'abord, comparer les éléments, comme dans l'arbre

   |
  /\
 |   |
/\ /\
x x x x

cela prend n-1 comparaisons et chaque élément est impliqué dans la comparaison au plus log n fois. Vous trouverez le plus grand élément gagnant.

Le deuxième plus grand élément doit avoir perdu un match pour le gagnant (il ne peut pas perdre un match à un autre élément), de sorte qu'il est le journal de n éléments, le gagnant a joué contre. Vous pouvez trouver lequel d'entre eux à l'aide de log n - 1 comparaisons.

L'optimalité est prouvé par adversaire argument. Voir https://math.stackexchange.com/questions/1601 ou http://compgeom.cs.uiuc.edu/~jeffe/enseignement/497/02-sélection.pdf ou http://www.imada.sdu.dk/~jbj/DM19/lb06.pdf ou https://www.utdallas.edu/~chandra/documents/6363/lbd.pdf

Utiliser la Bulle de tri ou de Sélection de l'algorithme de tri qui trie le tableau par ordre décroissant. Ne pas trier le tableau complètement. Seulement deux passes. Premier passage donne le plus grand élément et le second passage vous donnera le deuxième plus grand élément.

Pas. des comparaisons de premier passage: n-1

Pas. des comparaisons de premier passage: n-2

Total no. de comparaison pour trouver le deuxième plus grand: 2n-3

Peut-être vous pouvez généraliser cet algorithme. Si vous avez besoin de la 3ème plus grande puis vous faire 3 passes.

Par la stratégie ci-dessus, vous n'avez pas besoin de toutes les variables temporaires comme la Bulle de tri et de Sélection, de tri sont en place le tri algorithmes.

cas 1-->9 8 7 6 5 4 3 2 1

cas 2--> 50 10 8 25 ........

cas 3--> 50 50 10 8 25.........

cas 4--> 50 50 10 8 50 25.......

public void second element()  
{
      int a[10],i,max1,max2;  
      max1=a[0],max2=a[1];  
      for(i=1;i<a.length();i++)  
      {  
         if(a[i]>max1)  
          {
             max2=max1;  
             max1=a[i];  
          }  
         else if(a[i]>max2 &&a[i]!=max1)  
           max2=a[i];  
         else if(max1==max2)  
           max2=a[i];  
      }  
}

Je sais que c'est une vieille question, mais voici ma tentative de le résoudre, rendant l'utilisation du Tournoi de l'Algorithme. Il est similaire à la solution utilisée par @sdcvvc , mais je suis à l'aide de tableau à deux dimensions pour stocker des éléments.

De faire fonctionner les choses, il y a deux hypothèses:

1) nombre d'éléments dans le tableau est la puissance de 2

2) il n'y a pas de doublons dans le tableau

L'ensemble du processus se compose de deux étapes:

1. la construction d'un tableau 2D en comparant deux par deux éléments. Première ligne du tableau 2D va être l'ensemble du tableau d'entrée. La ligne suivante contient les résultats des comparaisons de la rangée précédente. Nous continuons à des comparaisons sur le nouveau tableau et de continuer à construire le tableau 2D jusqu'à ce qu'un tableau d'un seul élément (le plus grand) est atteint.

2. nous avons un 2D-tableau où la dernière ligne contient un seul élément: la plus grande. Nous continuons d'aller du bas vers le haut, dans chaque tableau de trouver l'élément qui a été "battu" par le plus grand et en la comparant à la "deuxième" de la valeur. Pour trouver l'élément battu par la plus grande, et pour éviter de O(n) comparaisons, il faut stocker l'indice du plus grand élément de la rangée précédente. De cette façon, nous pouvons facilement vérifier les éléments adjacents. À n'importe quel niveau (au-dessus de niveau de la racine),les éléments adjacents sont obtenus:

leftAdjacent = rootIndex*2
rightAdjacent = rootIndex*2+1,

où rootIndex est l'indice de la plus grande(la racine) de l'élément au niveau précédent.

Je sais que la question demande pour le C++, mais voici ma tentative de le résoudre en Java. (J'ai utilisé des listes au lieu de tableaux, pour éviter le désordre changement de la taille de la matrice et/ou inutiles tableau de calcul de la taille)

public static Integer findSecondLargest(List<Integer> list) {
        if (list == null) {
            return null;
        }
        if (list.size() == 1) {
            return list.get(0);
        }
        List<List<Integer>> structure = buildUpStructure(list);
        System.out.println(structure);
        return secondLargest(structure);

    }

    public static List<List<Integer>> buildUpStructure(List<Integer> list) {
        List<List<Integer>> newList = new ArrayList<List<Integer>>();
        List<Integer> tmpList = new ArrayList<Integer>(list);
        newList.add(tmpList);
        int n = list.size();
        while (n>1) {
            tmpList = new ArrayList<Integer>();
            for (int i = 0; i<n; i=i+2) {
                Integer i1 = list.get(i);
                Integer i2 = list.get(i+1);
                tmpList.add(Math.max(i1, i2));
            }
            n/= 2;
            newList.add(tmpList);   
            list = tmpList;
        }
        return newList;
    }

    public static Integer secondLargest(List<List<Integer>> structure) {
        int n = structure.size();
        int rootIndex = 0;
        Integer largest = structure.get(n-1).get(rootIndex);
        List<Integer> tmpList = structure.get(n-2);
        Integer secondLargest = Integer.MIN_VALUE;
        Integer leftAdjacent = -1;
        Integer rightAdjacent = -1;
        for (int i = n-2; i>=0; i--) {
            rootIndex*=2;
            tmpList = structure.get(i);
            leftAdjacent = tmpList.get(rootIndex);
            rightAdjacent = tmpList.get(rootIndex+1); 
            if (leftAdjacent.equals(largest)) {
                if (rightAdjacent > secondLargest) {
                    secondLargest = rightAdjacent;
                }
            }
            if (rightAdjacent.equals(largest)) {
                if (leftAdjacent > secondLargest) {
                    secondLargest = leftAdjacent;
                }
                rootIndex=rootIndex+1;
            }
        }

        return secondLargest;
    }

La version de PHP de le Gumbo algorithme: http://sandbox.onlinephpfunctions.com/code/51e1b05dac2e648fd13e0b60f44a2abe1e4a8689

$numbers = [10, 9, 2, 3, 4, 5, 6, 7];

$largest = $numbers[0];
$secondLargest = null;
for ($i=1; $i < count($numbers); $i++) {
    $number = $numbers[$i];
    if ($number > $largest) {
        $secondLargest = $largest;
        $largest = $number;
    } else if ($number > $secondLargest) {
        $secondLargest = $number;
    }
}

echo "largest=$largest, secondLargest=$secondLargest";

de l'essayer.

max1 = a[0].
max2.
for i = 0, until length:
  if a[i] > max:
     max2 = max1.
     max1 = a[i].
     #end IF
  #end FOR
return min2.

il doit travailler comme un charme. faible complexité.

voici un code java.

int secondlLargestValue(int[] secondMax){
int max1 = secondMax[0]; //assign the first element of the array, no matter what, sorted or not.
int max2 = 0; //anything really work, but zero is just fundamental.
   for(int n = 0; n < secondMax.length; n++){ //start at zero, end when larger than length, grow by 1. 
        if(secondMax[n] > max1){ //nth element of the array is larger than max1, if so.
           max2 = max1; //largest in now second largest,
           max1 = secondMax[n]; //and this nth element is now max.
        }//end IF
    }//end FOR
    return max2;
}//end secondLargestValue()

#include<stdio.h>
main()
{
        int a[5] = {55,11,66,77,72};
        int max,min,i;
        int smax,smin;
        max = min = a[0];
        smax = smin = a[0];
        for(i=0;i<=4;i++)
        {
                if(a[i]>max)
                {
                        smax = max;
                        max = a[i];
                }
                if(max>a[i]&&smax<a[i])
                {
                        smax = a[i];
                }
        }
        printf("the first max element z %d\n",max);
        printf("the second max element z %d\n",smax);
}

Je suis passé par tous les postes ci-dessus, mais je suis convaincu que la mise en œuvre du Tournoi de l'algorithme est la meilleure approche. Considérons l'algorithme suivant posté par @Gumbo

largest := numbers[0];
secondLargest := null
for i=1 to numbers.length-1 do
    number := numbers[i];
    if number > largest then
        secondLargest := largest;
        largest := number;
    else
        if number > secondLargest then
            secondLargest := number;
        end;
    end;
end;

Il est très bon dans le cas où allons-nous trouver le deuxième plus grand nombre dans un tableau. Il a (2n-1) nombre de comparaisons. Mais que faire si vous voulez calculer le troisième plus grand nombre ou de certains kth plus grand nombre. L'algorithme ci-dessus ne fonctionne pas. Vous avez obtenu d'une autre procédure.

Donc, je crois tournoi algorithme approche est la meilleure et c'est ici la lien pour que.

Il peut être fait dans n + ceil(log n) - 2 comparaison.

Solution:
il prend n-1 comparaisons pour obtenir le minimum.

Mais pour obtenir le minimum, nous allons organiser un tournoi dans lequel chaque élément seront regroupés par paires. comme un tournoi de tennis et gagnant d'un tour d'aller de l'avant.

Hauteur de cet arbre sera log n depuis que nous avons la moitié à chaque tour.

Idée d'avoir une deuxième, au minimum, qu'il sera battu par minimum candidat dans l'une des tours précédents. Donc, nous avons besoin de trouver le minimum de candidats potentiels (battu par minimum).

Des candidats potentiels seront log n = hauteur de l'arbre

Donc, pas de. de comparaison pour trouver le minimum à l'aide de tournoi est un arbre n-1
et pour la seconde minimum est log n -1
résume = n + ceil(log n) - 2

Voici le code C++

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>

using namespace std;

typedef pair<int,int> ii;

bool isPowerOfTwo (int x)
{
  /* First x in the below expression is for the case when x is 0 */
  return x && (!(x&(x-1)));
}
//modified
int log_2(unsigned int n) {
    int bits = 0;
    if (!isPowerOfTwo(n))
        bits++;
    if (n > 32767) {
        n >>= 16;
        bits += 16;
    }
    if (n > 127) {
        n >>= 8;
        bits += 8;
    }
    if (n > 7) {
        n >>= 4;
        bits += 4;
    }
    if (n > 1) {
        n >>= 2;
        bits += 2;
    }
    if (n > 0) {
        bits++;
    }
    return bits;
}

int second_minima(int a[], unsigned int n) {

    //build a tree of size of log2n in the form of 2d array
    //1st row represents all elements which fights for min
    //candidate pairwise. winner of each pair moves to 2nd
    //row and so on
    int log_2n = log_2(n);
    long comparison_count = 0;
    //pair of ints : first element stores value and second
    //               stores index of its first row
    ii **p = new ii*[log_2n];
    int i, j, k;
    for (i = 0, j = n; i < log_2n; i++) {
        p[i] = new ii[j];
        j = j&1 ? j/2+1 : j/2;
    }
    for (i = 0; i < n; i++)
        p[0][i] = make_pair(a[i], i);



    //find minima using pair wise fighting
    for (i = 1, j = n; i < log_2n; i++) {
        //for each pair
        for (k = 0; k+1 < j; k += 2) {
            //find its winner
            if (++comparison_count && p[i-1][k].first < p[i-1][k+1].first) {
                p[i][k/2].first = p[i-1][k].first;
                p[i][k/2].second = p[i-1][k].second;
            }
            else {
                p[i][k/2].first = p[i-1][k+1].first;
                p[i][k/2].second = p[i-1][k+1].second;
            }

        }
        //if no. of elements in row is odd the last element
        //directly moves to next round (row)
        if (j&1) {
            p[i][j/2].first = p[i-1][j-1].first;
            p[i][j/2].second = p[i-1][j-1].second;
        }
        j = j&1 ? j/2+1 : j/2;
    }



    int minima, second_minima;
    int index;
    minima = p[log_2n-1][0].first;
    //initialize second minima by its final (last 2nd row)
    //potential candidate with which its final took place
    second_minima = minima == p[log_2n-2][0].first ? p[log_2n-2][1].first : p[log_2n-2][0].first;
    //minima original index
    index = p[log_2n-1][0].second;
    for (i = 0, j = n; i <= log_2n - 3; i++) {
        //if its last candidate in any round then there is
        //no potential candidate
        if (j&1 && index == j-1) {
            index /= 2;
            j = j/2+1;
            continue;
        }
        //if minima index is odd, then it fighted with its index - 1
        //else its index + 1
        //this is a potential candidate for second minima, so check it
        if (index&1) {
            if (++comparison_count && second_minima > p[i][index-1].first)
                second_minima = p[i][index-1].first;
        }
        else {
            if (++comparison_count && second_minima > p[i][index+1].first)
                second_minima = p[i][index+1].first;
        }
        index/=2;
        j = j&1 ? j/2+1 : j/2;
    }


    printf("-------------------------------------------------------------------------------\n");
    printf("Minimum          : %d\n", minima);
    printf("Second Minimum   : %d\n", second_minima);
    printf("comparison count : %ld\n", comparison_count);
    printf("Least No. Of Comparisons (");
    printf("n+ceil(log2_n)-2) : %d\n", (int)(n+ceil(log(n)/log(2))-2));
    return 0;
}

int main()
{
    unsigned int n;
    scanf("%u", &n);
    int a[n];
    int i;
    for (i = 0; i < n; i++)
        scanf("%d", &a[i]);
    second_minima(a,n);
    return 0;
}

Une bonne façon avec O(1) fois la complexité serait d'utiliser un max-heap. Appelez le heapify deux fois et vous avez la réponse.

Je suppose, suivez l'algorithme optimal utilise n+log n-2 comparaisons" à partir de ci-dessus, le code que j'ai trouvé qui n'utilise pas d'arbre binaire pour stocker la valeur serait la suivante:

Lors de chaque appel récursif, la taille de la matrice est réduit de moitié.

De sorte que le nombre de comparaisons est:

1ère itération: n/2 comparaisons

2ème itération: n/4 comparaisons

3ème itération: n/8 comparaisons

...
Jusqu'à log n itérations?

Par conséquent, total => n - 1 comparaisons?

function findSecondLargestInArray(array) {
    let winner = [];
    if (array.length === 2) {
        if (array[0] < array[1]) {
            return array[0];
        } else {
            return array[1];
        }
    }
    for (let i = 1; i <= Math.floor(array.length /2); i++) {
        if (array[2 * i - 1] > array[2 * i - 2]) {
            winner.push(array[2 * i - 1]);
        } else {
            winner.push(array[2 * i - 2]);
        }
    }
    return findSecondLargestInArray(winner);
}

En supposant tableau contient 2^n certain nombre de numéros.

Si il y a 6 chiffres, puis 3 numéros de passer au niveau suivant, ce qui n'est pas droit.

Besoin de 8 chiffres => 4 => 2 => 1 numéro => 2^n nombre de nombre

class solution:
def SecondLargestNumber (self,l):
    Largest = 0
    secondLargest = 0
    for i in l:
        if i> Largest:
            secondLargest = Largest
        Largest = max(Largest, i)
    return Largest, secondLargest