数组中的第k个最大元素

题目描述：

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

思路：

看到题目最先先到的是：快排（幸运的话一次就能排到第k大(o(n))，不幸运的话可能需要n次，时间复杂度为n^2.

或者冒泡排序/选择排序/插入排序，时间复杂度为nk。

但是题目要求时间复杂度为O(n),

然后隔了一段时间再看这个题想到用最大堆或最小堆，java没有这两种堆，但是有优先队列，要找第k大，即第nums.length-k+1小的值，我们可以将当前遍历到的元素中前nums.length-k+1的元素存入优先队列（这个队列我们让其从大到小排序）：

队列size小于nums.length-k+1时直接加入队列，当队列size达到nums.length-k+1时，新元素与队首元素（当前队列中的最大值）作比较，若小于该值，则删除原来的队首元素，将其加入队列，否则不做处理，这样就可以保证第nums.length-k+1小的元素即第k大的元素一直在这个优先队列的队首。最后返回这个队首值即可。

这样虽然能提交通过，但是其实优先队列插入新元素的时间复杂度为logn，所以严格来算时间复杂度是可能超过o(n)的。

题解中的思路：

题解中主要是两种思路：

1是利用快速排序，根据每次找到的元素的正确下标与k做比较，然后缩小下次快排的范围

2.就是利用小根堆大根堆优先队列，但是有时会要求不能直接使用优先队列，这就需要我们自己构造大根堆并提供添加元素与删除栈顶元素的方法。

代码：

public static int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2-o1;
        }
    });
    for (int i = 0; i < nums.length; i++) {
        if(queue.size()<nums.length+1-k){
            queue.add(nums[i]);
            //continue;
        }else{
            if(queue.peek()>=nums[i]){
                queue.poll();
                queue.add(nums[i]);
            }
        }
    }
    return queue.peek();

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

手动实现小根堆的代码：

class Solution {
    public int findKthLargest(int[] nums, int k) {
        //对数组中前k个元素构建小根堆
        for(int i = 0; i < k; i++){
            swim(i, nums);
        }
        //对剩余元素与堆顶元素比较，比堆顶元素小抛掉，比堆顶元素大，替换掉堆顶元素并下沉到正确位置，始终维持堆的大小为K，最后大小为K的堆的堆顶元素及为第K大元素，返回答案
        for(int i = k; i < nums.length; i++){
            if(nums[i] > nums[0]){
                swap(i, 0, nums);
                sink(0, nums, k);
            }
        }
        return nums[0];
    }

    private boolean comparator(int v1, int v2){
        return v1 < v2;
    }
    //上浮操作，对二叉堆数组中下标为i的数进行上浮操作
    private void swim(int i, int[] heap){
        while(i > 0 && comparator(heap[i], heap[(i - 1) / 2])){
            swap(i, (i - 1) / 2, heap);
            i = (i - 1) / 2;
        }
    }
    //下沉操作，对二叉堆数组中下标为i的数进行下沉操作
    private void sink(int i, int[] heap, int heapSize){
        while(2 * i + 1 <= heapSize - 1){
            int j = 2 * i + 1;
            if(j + 1 <= heapSize - 1 && comparator(heap[j + 1], heap[j])){
                j++;
            }
            if(comparator(heap[i], heap[j])){
                break;
            }
            swap(i, j, heap);
            i = j;
        }
    }
    
    private void swap(int i , int j, int[] nums){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47