寻找数组中第k大的元素

问题陈述

寻找数组中第k大的元素。

算法实现

思路一：先排序，然后直接获取。

1
2
3
4
public int getKLargeElements(int[] nums,int k){
    Arrays.sort(nums);
    return nums[nums.length-k];
}

思路二：通过维持一个大堆顶，堆顶元素就是第k大的元素。

1
2
3
4
5
6
7
8
9
public int getKLargeElements(int[] nums,int k){
    PriorityQueue<Integer> pq=new PriorityQueue<>();//默认实现一个小顶堆。
    for(int num:nums){
        pq.add(num);
        if(pq.size()>k){
            pq.poll();
        }
    }
}

思路三：快速选择排序

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
class Solution{
    Random random=new Random();
    public int getKLargeElements(int[] nums,int k){
        return quicksort(nums,0,nums.length-1,nums.length-k)
    }
    public int quicksort(int[] nums,int l,int r,int index){
        int q=randomPartition(nums,l,r);
        if(q==index){
            return nums[q];
        } else{
            return q<index? quicksort(nums,q+1,r,index):quicksort(nums,l,q-1,index);
        }
        
    }
    public int randomPartition(int[] nums,int l,int r){
        int i = random.nextInt(r - l + 1) + l;
        swap(a, i, r);
        return partition(a, l, r);
    }
    public int partition(int[] a, int l, int r) {
        int x = a[r], i = l - 1;
        for (int j = l; j < r; ++j) {
            if (a[j] <= x) {
                swap(a, ++i, j);
            }
        }
        swap(a, i + 1, r);
        return i + 1;
    }

    public void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}