n个无序数求第k大的数

发表于

今天面试问到n个无序的库找出第k大的数，用最优的算法，想了半天只后只好回答用快速排序再求第k大的数，时间复杂度为O(nlogn)，但这显然不是最优算法，回来后查了一个，在此做个记录。主要参考: 寻找第k大的数

排序解决法

排序再找第k大的数是最简单的解决方法，排序完成后再找只需要根据数据索引即可，时间复杂度是1

而排序最优的是快速排序(不是绝对的，与数组大小有关)，时间复杂度为O(nlogn)，所以最后的时间复杂度O(nlogn)

快速排序基本思想是数组中取任意一个值key，将大于key的值放在key右边，小于key的值放在key左边。key的左边和右边则都是有序的了，然后递归key值左右的子数组。具体代码见参考文章。

类快排解法

采取快速排序的思想，快速排序中一个最重要的partition算法是这样的。

快速排序基本思想是数组中取任意一个值key，将大于key的值放在key右边，小于key的值放在key左边。key的左边和右边则都是有序的了

快排中的partition算法，返回key在数组中的位置，如果key的位置正好等于k-1，那么问题则得到解决，如果key的位置不等于k-1，可使用递归查找对应子数组。直到key的位置等于k-1，则找对问题的解。

此解法的效率值为N*lgK，由于K是常数，所以此解法效率值为N，优于排序解法

通俗的描述一下partition的过程

  1. 长度为n的数组，取出第1个数作为参考值m，从第n个数向前遍历
  2. 如果数小于m则将该数放到第一个数的位置，并记下索引j
  3. 再从第2个数向后遍历，如果数大于m，则将该数放到数组索引j的位置，并记下该数的索引i
  4. 再从数组索引j-1的位置向前遍历，如果数小于m，将该数放到数组索引i的位置，并记下此时的索引j
  5. 再次从i+1的位置向后遍历，循环3-4
  6. 最后空的就是m的位置，而且m左边的比m小，右边的比m大

最小堆解法

要先了解堆排序: 堆排序及优先队列

先在此总结一下堆排序的特性

  1. 堆是一个完全二叉树的数据结构，最大堆是父节点上的值比子节点上的值大，反之则是最小堆
  2. 堆是以数组形式实现的，所以二及对中i节点的左子节点一定是2i+1，右子节点一定是2i+2，而且数组中 array.length/2 到 array.length - 1之间的节点，肯定是叶子节点，没有子节点
  3. 创建堆要逆序进行，也就是从array.length/2开始，这样才能保证父节点一定大于子节点
  4. 堆排序其实就是将创建好的堆的最根节点放到数组最后，然后再次从根节点创建最大堆的过程

根据最大堆的排序过程可以看到，每次都是从堆中选取最大的数放到数组，所以在要算出第k个数时就可以停止了。

1
2
3
4
5
6
7
8
9
10
11
12
public static int findKByHeap(int[] array, int k) {
    buildHeap(array, k);
    for (int i = k + 1; i < array.length; i++) {
        if (array[i] > array[0]) {
            int temp = array[i];
            array[i] = array[0];
            array[0] = temp;
            maxHeapify(array, k, 0);
        }
    }
    return array[0];
}