题目描述

给定一个整数数组num，同时给定它的大小n和要找的K(K在1到n之间)，请返回第K大的数，保证答案存在。如输入数组[1,3,5,2,2],5,3，返回：2。

类似题目

解题思路

• 快速排序 & 分治法：每次可以将一个元素放到最终位置上，所以如果当前放置的元素是第K个位置，即得到了最终的结果，不用继续进行排序操作。
• 最大堆：维护k个元素的最大堆，原理与上述第2个方案一致，即用容量为k的最小堆存储最先遍历到的k个数，并假设它们即是最小的k个数，建堆费时O（k），有k1<k2<...kmax（kmax设为最大堆中的最小元素）。继续遍历数列，每次遍历一个元素x，与堆顶元素比较，若x<kmax，则更新堆（用时logk），否则不更新堆。这样下来，总费时O（k+（n-k）logk）=O（NlogK）。此方法得益于在堆中，查找等各项操作时间复杂度均为logk（不然，就如上述思路2所述：直接用数组也可以找出最大的k个元素，用时O（n*k））。

代码实现

快速排序

public class FindKthNum {
    public int findKthNum(int[] num, int len, int k) {
        return quickSort(num, 0, len - 1, k);
    }

    private int quickSort(int[] num, int low, int high, int k) {
        if (low <= high) {
            int pos = partition(num, low, high);
            if (pos == k - 1)
                return num[pos];
            else if (pos > k - 1)
                return quickSort(num, low, pos - 1, k);
            else
                return quickSort(num, pos + 1, high, k);
        } else
            return -1;
    }

    /**
     * 求第K大时在（1）（2）中按从大到小排序、求第K小时在（1）（2）中按从小到大排序，只改变大于号、小于号即可。
     * 现在是从大到小排序求第K大
     */
    private int partition(int[] num, int low, int high) {
        int tmp = num[low];
        while (low < high) {
            while ((low < high) && tmp >= num[high])//（1）
                high--;
            num[low] = num[high];
            while ((low < high) && tmp <= num[low]) //（2）
                low++;
            num[high] = num[low];
        }
        num[low] = tmp;
        return low;
    }

    public static void main(String[] args) {
        FindKthNum obj = new FindKthNum();
        System.out.println(obj.findKthNum(new int[]{1, 3, 5, 2, 2}, 5, 3));
    }
}

最大堆

public int findKthNum(int[] input, int k) {
    int length = input.length;
    if (k > length || k == 0) return 0;

    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2.compareTo(o1);
        }
    });
    for (int i = 0; i < length; i++) {
        if (maxHeap.size() != k) {
            maxHeap.offer(input[i]);
        } else if (maxHeap.peek() > input[i]) {
            Integer temp = maxHeap.poll();
            temp = null;
            maxHeap.offer(input[i]);
        }
    }

    int count = 0;
    for (Integer integer : maxHeap) {
        if (++count == k)
            return integer;
    }
    return 0;
}

同理可以得到求前K个最小数的代码：

public ArrayList<Integer> getKLeastNumbers(int[] input, int k) {
    ArrayList<Integer> result = new ArrayList<>();
    int length = input.length;
    if (k > length || k == 0) {
        return result;
    }
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2.compareTo(o1);
        }
    });
    for (int i = 0; i < length; i++) {
        if (maxHeap.size() != k) {
            maxHeap.offer(input[i]);
        } else if (maxHeap.peek() > input[i]) {
            Integer temp = maxHeap.poll();
            temp = null;
            maxHeap.offer(input[i]);
        }
    }
    for (Integer integer : maxHeap) {
        result.add(integer);
    }
    return result;
}

参考资料

寻找给定区间内的第k小（大）的元素
寻找第K小的数
寻找最小的k个数 The-Art-Of-Programming-By-July
第三章续：Top K算法问题的实现
寻找第K大数的方法小结
寻找第K大的数的方法总结