【算法】16个无序数最多20次比较找到第二大的数

本文主要是介绍【算法】16个无序数最多20次比较找到第二大的数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这个题是刚刚在微博上看到的，第一想法就想到了leetcode上关于注水的题，Trapping Rain Water，当时的解法是这样的：通过求第二大的数，来解决注水问题

class Solution {
public:int trap(int A[], int n) {int left = 0;int right = n-1;int trap = 0;int secHigh = 0;while (left < right){if(A[left] < A[right]){secHigh = max(A[left], secHigh);trap += secHigh;left++;}else{secHigh = max(A[right], secHigh);trap += secHigh;right--;}}return trap;}
};

看到代码也可以知道，一次判断left与right，一次判断max，这样每个数就有两次比较，而16个数也要30次比较，很明显不能满足要求。
后来看到某牛人的解法，叙述如下：
1、16个数分两组，每组8个，进行两两比较选择较大的，得到8个较大数的数组。这样有8次比较。
2、将8个数同样分两组，得到4个数，这样有4次比较。
3、在继续划分，则有2次比较，最后得到一次比较，这样共8+4+2+1=15次比较得到了最大数M。
4、第二大的数为与最大数进行过比较的数，一共有4个，在这4个数中找到最大的即为整个数组中第二大数S。这样有3此比较，则一共有15+3=18次比较。
关于第4步的解释如下：M最大，M比其他数都大，则M一定会剩下，如果S与M进行比较，则S属于与M比较的数组内，如果S与其他数比较，则S一定会剩下，那么S一定会与M进行比较，所以S一定存在于与M进行过比较的数组内。
举例如下：
数组{5, 3, 12, 14, 1, 8, 9, 13 , 4, 16, 10, 6, 7, 11, 2, 15}
第一次比较：共8次比较
第一组：5, 3, 12, 14, 1, 8, 9, 13 ,
第二组：4，16, 10, 6, 7, 11, 2, 15
剩下：5,16,12,14， 7,11,9,15 共4次比较
同样比较剩下：7,16， 12,15 共2次比较
继续：12,16 共1次比较
最后得到：16
与16比较过的数为：12,15,11,3 共3次比较
其中最大的为15，所以数组中第二大数为15. 共比较18次。