[leetcode]215. Kth Largest Element in an Array

Analysis

好冷鸭~会下雪么—— [每天刷题并不难0.0]

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.

排序一下就行了，ummm。。

Implement

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        //reverse(nums.begin(), nums.end());
        return nums[nums.size()-k];
    }
};

其实这道题跟快排的过程差不多，但是不用全部排好序，只要找到第k大的元素就行了，但是这个时间不如第一种快，哈哈

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int left = 0;
        int right = nums.size()-1;
        while(true){
            int p = partition(nums, left, right);
            if(p == k-1)
                return nums[p];
            else if(p < k-1)
                left = p+1;
            else
                right = p-1;
        }
    }
    int partition(vector<int>& nums, int left, int right){
        int p = nums[left];
        int l = left+1;
        int r = right;
        while(l <= r){
            if(nums[l]<p && nums[r]>p){
                swap(nums[l], nums[r]);
                l++;
                r--;
            }
            if(nums[l] >= p)
                l++;
            if(nums[r] <= p)
                r--;
        }
        swap(nums[left], nums[r]);
        return r;
    }
};

当然也可以用堆来实现,这个跟第一种方法差不多快

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> pq;
        for(int num:nums){
            pq.push(num);
            if(pq.size() > k)
                pq.pop();
        }
        return pq.top();
    }
};