第二大的数

Find the second largest number in an array.

首先，一个简单直观的想法：两次遍历数组，第一次找到最大的数，然后第二次找到除了最大的这个数之外的最大的数。如果没有重复的元素，需要n-1+n-2次比较就能得到结果。
然而事实上问题的定义是不够明确的。在开始想解法之前，至少有以下这些问题需要明确

a. 这些数据是什么？人的年龄？工资？还是随机生成的范围不确定是一堆数？
b. 这个数组是给定之后就不变的，还是经常有增删操作的？
c. 获取第二大的数这个操作是否经常被使用？
d. 需求是否会变动？比如突然要求找第3大的，第9大的数？

如果这些数是某个公司的员工号，或者员工的年龄呢这样的元素呢？ 当然上面的解法依然可以用。但或许更通用的解法是先把数组排序，这样可以轻松地扩展成找第k大的元素的算法：排序，然后输出倒数第k个元素。

而像人的年龄这样范围已知且这个范围并不大的数据类型，采用诸如基数排序、计数排序这类分配式排序算法，时间复杂度是O(n)。如果需要经常获取这个第二大的数，那我们在前期花费一些时间来排序，使得此后的操作都是O(1)的，这样整体效率更高，何乐而不为呢？

但如果数组经常被增删改，分配式排序就不是那么高效了，因为要经常重新排序。这种情况下堆排序的效率会更高些：插入或删除一个元素的操作都是O(logn)时间，而获得第k大的元素则大致是O(klogn)。

如果我们的输入数据范围未知，数组不可变，就现在要你给出第二大的数，怎样才能使得元素间的比较次数尽量少呢？
可以采用两两比较的锦标赛(tournament)策略。就跟遗传算法里的锦标赛选择策略一样样的。
这种策略会形成一种分层比赛的结构，就好像篮球赛，从小组赛，到四分之一，到半决，决赛...我们把数组中元素两两分组，比较，优胜者进入下一轮比赛，再分组，比赛...直到最后只有一位优胜者，这就是最大的数。然后第二大的那个数之所以没有笑到最后，是因为它在某次比较中被干掉了，而能干掉第二大的数的，只有这个最大的数了，说明最大的数已经和第二大的数进行过比较了。因此接下来要做的就是，把在每一层比较中被最大数干掉的那些数收集起来，让它们再来一次这样逐层的比较，胜出者便是第二大的数了。
比如给定的数组是这样的：
{4,8,1,3,6,10,7,9,13,2,15,5,16,11,14,12}
分组：{4,8, 1,3, 6,10, 7,9, 13,2, 15,5, 16,11, 14,12}
比较得：{8,3,10,9,13,15,16,14}
分组：{8,3, 10,9, 13,15, 16,14}
比较得{8,10,15,16}
分组:{8,10 ,15,16}
比较得{10, 16}
分组：{ 10,16 }
比较得16， 为是最大值。这里一共用了8+4+2+1=15=n-1次比较。
同时能得到{11,14,15,10}这logn=4个与16竞赛时落败的数。对它们重复上述过程，需要2+1=3=logn -1次比较。如此便花费了n-1+logn-1次比较，得到数组中第二大的数。

如果像LeetCode#215那样要求数组中第k大的数，可以借鉴快速排序算法中的划分函数的思想。随机选择一个划分参照，划分后得到它的位置p，如果p在超过了第k大的位置，则把范围缩小到左边，继续找第k大的数；如果p没有超过第k大的位置，则把范围缩小到p的右边，找这边的第k-p+1大的数。

//java
    public int findKthLargest(int[] nums, int k) {
        int left=0, right=nums.length-1;
        if(left>right || k>nums.length)
            return -1;
        while(left<right){
            int p=partition(nums, left, right);
            if(p+1==k)
                return nums[p];
            else if(p+1>k)
                right=p-1;  
            else
                left=p+1;
                
        }
        return nums[left];
    }
    private static int partition(int[] a, int lo, int hi){
        int pivot=a[lo];
        int i=lo, j=hi+1;
        while(true){
            while(a[++i]>=pivot && i<hi);
            while(a[--j]<=pivot && j>lo);
            if(i>=j) break;
            swap(a, i, j);
        }
        swap(a, lo, j);
        return j;
    }
    private static void swap(int[] a, int i, int j){
        int tmp=a[i];
        a[i]=a[j];
        a[j]=tmp;
    }

此算法的最差时间复杂度是O(n^2)，而平均时间复杂度是O(n)。证明过程类似快排，略。