找到第二个最大数组数n + log 2（n）-2比较

Question

给出一个n个不同数的非排序数组，其中n是2的幂。给出一个算法，用于标识第二大并且最多使用n + log 2（n）-2个比较。

Answer 1

1. 从比较奇数和偶数位置的n元素数组的元素开始，并确定每对的最大元素。这一步需要n/2次比较。现在你只有n/2个元素。继续配对比较以获得n/4，n/8，...元素。当发现最大的元素时停止。这一步需要总共n/2 + n/4 + n/8 + ... + 1 = n-1个比较。
2. 在上一步骤中，最大元素立即与log 2（n）其他元素比较。您可以在log₂（n）-1比较中确定这些元素中最大的元素。这将是阵列中第二大的数字。

---

实施例：8个数字[10,9,5,4,11,100,120,110]的数组。

比较级别1：[10,9] - > 10 [5,4] - > 5，[11,100] - > 100,[120,110] - > 120。

比较级别2：[10,5] - > 10 [100,120] - > 120。

比较级别3：[10,120] - > 120。

最大值为120.立即与10（第3级），100（第2级），110（第1级）比较。

第2步应该找到10,100和110的最大值。这是110.这是第二大元素。

Answer 2

问题是： 比方说，在比较级别1中，算法需要记住所有的数组元素，因为最大值还不知道，那么，第二，最后，第三。通过通过赋值跟踪这些元素将调用额外的值赋值，稍后当最大值已知时，还需要考虑追踪回来。结果，它不会比简单的2N-2比较算法快得多。而且，由于代码更复杂，您还需要考虑潜在的调试时间。
例如：在PHP中，运行时间进行比较VS值分配大致为：比较：（11-19），以值分配：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实施

 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

为什么不使用哈希算法给定数组[n]？它运行c * n，其中c是检查和散列的恒定时间。它做了n次比较。

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

还是我只是不明白的问题...

Answer 7

在Python2.7：下面的代码工作在O（n日志日志N）的额外排序。任何优化？

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

我已经在@Evgeny Kluev回答了Java中实现了这个算法。总的比较是n + log2（n）-2。还有一个很好的参考： http://users.csc.calpoly.edu/~dekhtyar/349-Spring2010/lectures/lec03.349.pdf。这与顶级投票算法类似。希望我的解决方案有帮助。谢谢。

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); 
} 

}