Trova il secondo numero più grande nella matrice al più n + log₂ (n) -2 confronti

Question

Viene fornito come input una matrice non ordinata di n numeri distinti, dove n è una potenza di 2. Fornire un algoritmo che identifica il secondo più grande numero nell'array e che utilizza al massimo n + log₂ (n) -2 confronti.

Answer 1

1. Iniziare confrontando gli elementi della matrice di elementi n in posizioni dispari e pari e determinando l'elemento più grande di ciascuna coppia. Questo passaggio richiede n/2 confronti. Ora hai solo n/2 elementi. Continua i confronti a coppie per ottenere n/4, n/8, ... elementi. Fermati quando viene trovato l'elemento più grande. Questo passaggio richiede un totale di n/2 + n/4 + n/8 + ... + 1 = confronti n-1.
2. Durante il passaggio precedente, l'elemento più grande è stato immediatamente confrontato con log₂ (n) altri elementi. È possibile determinare il più grande di questi elementi nei confronti di log₂ (n) -1. Quello sarebbe il secondo numero più grande dell'array.

---

Esempio: array di 8 numeri [10,9,5,4,11,100,120,110].

Confronto sul livello 1: [10,9] -> 10 [5,4] -> 5, [11,100] -> 100, [120,110] -> 120.

Confronto sul livello 2: [10,5] -> 10 [100,120] -> 120.

Confronti sul livello 3: [10,120] -> 120.

Il numero massimo è 120. È stato immediatamente confrontato con: 10 (livello 3), 100 (livello 2), 110 (livello 1).

Il passaggio 2 dovrebbe trovare il massimo di 10, 100 e 110. Che è 110. Questo è il secondo elemento più grande.

Answer 2

il problema è: diciamo, nel livello di confronto 1, l'algoritmo deve essere ricordato di tutto l'elemento dell'array perché il più grande non è ancora noto, quindi, secondo, infine, terzo. Continuando a tenere traccia di questi elementi tramite l'assegnazione, si invocherà un'ulteriore assegnazione di valore e in seguito, quando il più grande è noto, sarà necessario considerare anche il rintracciamento. Di conseguenza, non sarà significativamente più veloce del semplice algoritmo di confronto 2N-2. Inoltre, poiché il codice è più complicato, è necessario anche pensare a potenziali tempi di debug.
es: in PHP, durata di confronto vs assegnazione valore approssimativamente a dire: Confronto: (11-19) per un'assegnazione di valori: 16.

Answer 3

I shall give some examples for better understanding. : 
example 1 : 
>12 56 98 12 76 34 97 23 
>>(12 56) (98 12) (76 34) (97 23) 
>>> 56 98 76 97 
>>>> (56 98) (76 97) 
>>>>> 98 97 
>>>>>> 98 

The largest element is 98 

Now compare with lost ones of the largest element 98. 97 will be the second largest. 

Answer 4

nlogn attuazione

 public class Test { 
      public static void main(String...args){ 
       int arr[] = new int[]{1,2,2,3,3,4,9,5, 100 , 101, 1, 2, 1000, 102, 2,2,2}; 
       System.out.println(getMax(arr, 0, 16)); 
      } 

     public static Holder getMax(int[] arr, int start, int end){ 
      if (start == end) 
      return new Holder(arr[start], Integer.MIN_VALUE); 
     else { 
      int mid = (start + end)/2; 
      Holder l = getMax(arr, start, mid); 
      Holder r = getMax(arr, mid + 1, end); 

      if (l.compareTo(r) > 0) 
      return new Holder(l.high(), r.high() > l.low() ? r.high() : l.low()); 
      else 
      return new Holder(r.high(), l.high() > r.low() ? l.high(): r.low()); 
     } 
     } 

    static class Holder implements Comparable<Holder> { 
     private int low, high; 
     public Holder(int r, int l){low = l; high = r;} 

    public String toString(){ 
     return String.format("Max: %d, SecMax: %d", high, low); 
    } 

    public int compareTo(Holder data){ 
     if (high == data.high) 
     return 0; 

     if (high > data.high) 
     return 1; 
     else 
     return -1; 
    } 

    public int high(){ 
     return high; 
    } 
    public int low(){ 
     return low; 
    } 
    } 

} 

Answer 5

public static int FindSecondLargest(int[] input) 
     { 
      Dictionary<int, List<int>> dictWinnerLoser = new Dictionary<int, List<int>>();//Keeps track of loosers with winners 
      List<int> lstWinners = null; 
      List<int> lstLoosers = null; 

      int winner = 0; 
      int looser = 0; 

      while (input.Count() > 1)//Runs till we get max in the array 
      { 
       lstWinners = new List<int>();//Keeps track of winners of each run, as we have to run with winners of each run till we get one winner 

       for (int i = 0; i < input.Count() - 1; i += 2) 
       { 
        if (input[i] > input[i + 1]) 
        { 
         winner = input[i]; 
         looser = input[i + 1]; 
        } 
        else 
        { 
         winner = input[i + 1]; 
         looser = input[i]; 
        } 

        lstWinners.Add(winner); 


        if (!dictWinnerLoser.ContainsKey(winner)) 
        { 
         lstLoosers = new List<int>(); 
         lstLoosers.Add(looser); 
         dictWinnerLoser.Add(winner, lstLoosers); 
        } 
        else 
        { 
         lstLoosers = dictWinnerLoser[winner]; 
         lstLoosers.Add(looser); 
         dictWinnerLoser[winner] = lstLoosers; 
        } 
       } 

       input = lstWinners.ToArray();//run the loop again with winners 
      } 

      List<int> loosersOfWinner = dictWinnerLoser[input[0]];//Gives all the elemetns who lost to max element of array, input array now has only one element which is actually the max of the array 

      winner = 0; 

      for (int i = 0; i < loosersOfWinner.Count(); i++)//Now max in the lossers of winner will give second largest 
      { 
       if (winner < loosersOfWinner[i]) 
       { 
        winner = loosersOfWinner[i]; 
       } 
      } 

      return winner; 
     } 

Answer 6

Perché non utilizzare questo algoritmo di hashing per l'array dato [n]? Esegue c * n, dove c è il tempo costante per il controllo e l'hash. E non fa confronti.

int first = 0; 
    int second = 0; 
    for(int i = 0; i < n; i++) { 
     if(array[i] > first) { 
      second = first; 
      first = array[i]; 
     } 
    } 

O sono io proprio non capisco la domanda ...

Answer 7

In Python2.7: Il seguente codice funziona in O (log n nlog) per l'ordinamento in più. Qualche ottimizzazione?

def secondLargest(testList): 
    secondList = [] 
    # Iterate through the list 
    while(len(testList) > 1): 
     left = testList[0::2] 
     right = testList[1::2] 

     if (len(testList) % 2 == 1): 
      right.append(0) 

     myzip = zip(left,right) 
     mymax = [ max(list(val)) for val in myzip ] 
     myzip.sort() 
     secondMax = [x for x in myzip[-1] if x != max(mymax)][0] 

     if (secondMax != 0): 
      secondList.append(secondMax) 
     testList = mymax 

    return max(secondList) 

Answer 8

ho implementato questo algoritmo in Java risposta da @Evgeny Kluev. I confronti totali sono n + log2 (n) -2. C'è anche un buon riferimento: http://users.csc.calpoly.edu/~dekhtyar/349-Spring2010/lectures/lec03.349.pdf. Questo è simile all'algoritmo più votato. Spero che la mia soluzione sia utile. Grazie.

public class op1 { 

private static int findSecondRecursive(int n, int[] A){ 
    int[] firstCompared = findMaxTournament(0, n-1, A); //n-1 comparisons; 
    int[] secondCompared = findMaxTournament(2, firstCompared[0]-1, firstCompared); //log2(n)-1 comparisons. 
    //Total comparisons: n+log2(n)-2; 
    return secondCompared[1]; 
} 

private static int[] findMaxTournament(int low, int high, int[] A){ 
    if(low == high){ 
     int[] compared = new int[2]; 
     compared[0] = 2; 
     compared[1] = A[low]; 
     return compared; 
    } 
    int[] compared1 = findMaxTournament(low, (low+high)/2, A); 
    int[] compared2 = findMaxTournament((low+high)/2+1, high, A); 
    if(compared1[1] > compared2[1]){ 
     int k = compared1[0] + 1; 
     int[] newcompared1 = new int[k]; 
     System.arraycopy(compared1, 0, newcompared1, 0, compared1[0]); 
     newcompared1[0] = k; 
     newcompared1[k-1] = compared2[1]; 
     return newcompared1; 
    } 
    int k = compared2[0] + 1; 
    int[] newcompared2 = new int[k]; 
    System.arraycopy(compared2, 0, newcompared2, 0, compared2[0]); 
    newcompared2[0] = k; 
    newcompared2[k-1] = compared1[1]; 
    return newcompared2; 
} 

private static void printarray(int[] a){ 
    for(int i:a){ 
     System.out.print(i + " "); 
    } 
    System.out.println(); 
} 

public static void main(String[] args) { 
    //Demo. 
    System.out.println("Origial array: "); 
    int[] A = {10,4,5,8,7,2,12,3,1,6,9,11}; 
    printarray(A); 
    int secondMax = findSecondRecursive(A.length,A); 
    Arrays.sort(A); 
    System.out.println("Sorted array(for check use): "); 
    printarray(A); 
    System.out.println("Second largest number in A: " + secondMax); 
} 

}