0%

LeetCode 215. Kth Largest Element in an Array

Posted on Edited on In

题目

原题在此
Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:
Input: [3,2,1,5,6,4] and k = 2
Output: 5

Example 2:
Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.

解析

方法一: 最大堆

使用优先队列维护一个大小为k的最大堆, 遍历数组, 当发现比堆底元素更大的值时移除堆顶元素.

方法二: 优先选择

先复习下快速排序这个经典分治算法的步骤:

  1. 随机选取区域中一个数字做pivot.
  2. 遍历并交换元素使得pivot左侧元素全部小于a[pivot], 右侧全部大于等于a[pivot].
  3. 对[left .. pivot-1], [pivot + 1 .. rigth] 重复上述操作.

也就是说, 每次”分组”操作后,一个数的最终位置就确定了. 在从小到大的排序过程中, 只要pivot在分组操作后落到了倒数第k个位置时, 答案就找到了.
否则, 如果pivot比k小, 就递归操作右区间, 如果pivot比k大就递归操作左区间. 因为这时两个区间已经按大小关系划分过, 总有一个区间是不需要再关心的.

代码

方法一

1
2
3
4
5
6
7
8
9
10
11
12
// std used
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
       priority_queue<int,vector<int>, greater<int>> pq;
        for(int n : nums) {
            pq.push(n);
            if(pq.size()>k) pq.pop();
        }
        return pq.top();
    }
};
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
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int size = nums.size();
        buildHeap(nums, size);
        for (int i = nums.size() - 1; i >= nums.size() - k + 1; --i) {
            swap(nums[0], nums[i]);
            --size;
            maxify(nums, 0, size);
        }
        return nums[0];
    }

private:
    void buildHeap(vector<int>& a, int size) {
        for(int i = size / 2; i >= 0; --i) {
            maxify(a, i, size);
        }
    }
    
    void maxify(vector<int>& a, int i, int size) {
        int l = i * 2 + 1, r = i * 2 + 2, max = i;
        if(l < size && a[l] > a[max]) max = l;
        if(r < size && a[r] > a[max]) max = r;
        if(max != i ) {
            swap(a[i], a[max]);
            maxify(a, max, size);
        }
    }
};

方法二

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
func findKthLargest(nums []int, k int) int {
    return partition(nums, 0, len(nums)-1, k)
}

func partition(nums []int, left int, right int, k int) int {
    if left == right {
        return nums[left]
    }
    
    p := right
    l := left
    r := right-1
    for l <= r {
        for (l <= r && nums[l] >= nums[p]) {
            l++
        }
        
        for (l <= r && nums[r] < nums[p]) {
            r--
        }
        
        if (l <= r) {
            nums[l], nums[r] = nums[r], nums[l]
            l++
            r--
        }
    }
    nums[l], nums[p] = nums[p], nums[l]
    p = l
    
    if (p > k-1) {
        return partition(nums, left, p-1, k)
    } else if (p < k-1) {
        return partition(nums, p+1, right, k)
    }
    return nums[p];
}