题目

题目意思是找到数组中第k大的元素
比如：

1
2
3
输入: [3,2,1,5,6,4], k = 2
排序后: [1,2,3,4,5,6], 第二大是5
输出: 5

方法一 partition

题目求第k大元素相当于求第Size(array)-k元素，可以使用快速排序的partition，因为partition会得到某个元素在排序后数组中的位置，利用此特性，每次计算T(n) = T(n/2) + O(n), 时间复杂度为T(n) = O(n)，但是遇到分布不均匀时，会出现T(n) = T(n-1) + O(n)，时间复杂度为T(n) = O(n^2)，leetcode的样例包括这种情况，所以pivot选择不好时，时间消耗反到比直接快排慢。

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
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        partition(nums, 0, nums.size()-1, nums.size() - k);
        return kth;
    }
    void partition(vector<int> & nums, int start, int end, int k) {
        int small = -1;
        int target = end;
        for (int index = 0; index < end; index++) {
            if (nums[index] <= nums[target]) {
                small++;
                swap(nums[small], nums[index]);
            }
        }
        small++;
        swap(nums[small], nums[target]);
        
        if (small == k) {
            kth = nums[small];
            return;
        } else if (small < k) {
            partition(nums, small+1, end, k);
        } else {
            partition(nums, start, small-1, k);
        }        
    }
    int kth = -1;
};

方法二 sort

时间复杂度O(nlgn)

1
2
3
4
5
6
7
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        return nums[nums.size()-k];
    }
};

方法三 partial_sort

stl自带部分排序方法partial_sort

1
partial_sort(RandomIt first, RandomIt middle, RandomIt last, Compare comp);

时间复杂度O((last-first)log(middle-first))

1
2
3
4
5
6
7
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        partial_sort(nums.begin(), nums.end()-k+1, nums.end());
        return nums[nums.size()-k];
    }
};

方法四 堆

可以维护大小为k的大根堆， 将所有元素放入堆中，在堆底的是第k大小的元素，需要pop() k-1次将第k大小元素拿出来。 构建大根堆需要O(n), 每次pop()需要O(lgn)，一共需要k-1次pop(), 故时间复杂度为T(n)=O(n)+(k-1)O(lgn) = klg(n)

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int> q(nums.begin(), nums.end());
        for (int i = 0; i < k-1; i++) {
            q.pop();
        }
        return q.top();
    }
};

构建堆过程：
构建小根堆