215. 数组中的第K个最大元素(简单)

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

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

说明:

你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array

思路1：

堆，使用优先队列

思路2：

快排中partition，k-1个比其大，就可以了

代码：

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) {
        int len = nums.length;
        //堆，使用优先队列,求k大值用最小堆,默认就是最小堆 否则用lambda，(a,b)->a-b;
        PriorityQueue<Integer> heap = new PriorityQueue<>(k);
        //第一次先存前k个
        for(int i=0;i<k;i++){
            heap.add(nums[i]);
        }
        //开始遍历
        for(int i=k;i<len;i++){
            Integer tmp = heap.peek();
            if(nums[i]>tmp){
                //弹出
                heap.poll();
                heap.add(nums[i]);
            }
        }
        return heap.peek();
    }
}

代码2：

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
class Solution {
    public int findKthLargest(int[] nums, int k) {
       //
        int left = 0;
        int right = nums.length-1;
        int target = k-1;
        //二分
        while(true){
            int pivot = partition(nums,left,right);
            if(target==pivot){
                return nums[pivot];
            }else if(target>pivot){
                left = pivot+1;
            }else{
                right = pivot-1;
            }
        }
        //return -1;
    }
    //快排
    public int partition(int[] a, int left,int right){
        int tmp = a[right];
        int p = left -1;
        for(int i=left;i<right;i++){
            if(a[i]>=tmp){
                p++;
                swap(a,i,p);
            }
        }
        swap(a,p+1,right);
        return p+1;
    }
    public void swap(int[] a,int i,int j){
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
}
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
class Solution {
    public int findKthLargest(int[] nums, int k) {
        //1.先直接来k个数来建小堆
        //2.后面遍历时，将堆排序完的第0位排出去，然后将新来的数加进去
        //3.最后堆里面就剩了k个数，第0位就是第k大的数
        //int[] a = new int[k];
        //for(int i = 0;i<k;i++){
        //    a[i] = nums[i];
        //}
        buildHeap(nums,k);
        for(int i = k;i< nums.length;i++){
            if(nums[i]>nums[0]){
                nums[0] = nums[i];
                heapAdjust(nums,0,k);
            }
        }
        return nums[0];
    }
    public void buildHeap(int[] a,int size){
        //从非叶子节点的最后一个节点开始
        for(int i = size/2-1;i>=0;i--){
            heapAdjust(a,i,size);
        }
    }


    public void heapAdjust(int[] a,int parent,int size){
        int tmp = a[parent];
        int child = parent*2 +1;
        while(child<size){
            //比较兄弟节点,找更小的
            if(child+1<size && a[child+1]<a[child]){
                child++;
            }
            //比较parent和child
            if(a[child]<tmp){
                a[parent] = a[child];
                parent = child;
                child = parent*2+1;
            }else {
                //这个break不加，就超时
                break;
            }
        }
        a[parent]  = tmp;
    }
}