Noob
0%

The kth largest element in array

发表于 更新于 分类于 ，

方法1：结合快排和二分的思想

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public int findKthLargest(int[] nums, int k) {
    if(nums == null || k < 1 || k > nums.length) return -1;
    return kthElement(nums, k, 0, nums.length - 1);
}

private int kthElement(int[] nums, int k, int beg, int end) {
    int t = partation(nums, beg, end);
    if(t + 1 == k) return nums[t];
    if(t + 1 < k) return kthElement(nums, k, t + 1, end);
    else return kthElement(nums, k, beg, t - 1);
}

private int partation(int[] nums, int beg, int end) {
    int tmp = nums[beg];
    int i = beg, j = end;
    while(i < j) {
        while(j > i && nums[j] <= tmp) --j;
        nums[i] = nums[j];
        while(i < j && nums[i] > tmp) ++i;
        nums[j] = nums[i];
    }
    nums[i] = tmp;
    return i;
}

方法2：最小堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> que = new PriorityQueue<>();
    for(int i : nums) {
        if(que.size() < k)
            que.add(i);
        else {
            if(que.peek() < i) {
                que.poll();
                que.add(i);
            }
        }
    }
    return que.poll();
}