[LeetCode] Kth Largest Element in an Array

Kth Largest Element in an Array

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.

For example,
Given [3,2,1,5,6,4] and k = 2, return 5.

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

Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.

解题思路：

1、基本的方法是先对数组排序，然后找到地k大的元素即可。两行代码。排序算法的时间复杂度为O(nlogn)。Leetcode的运行时间是8ms。

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

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        quickSortVariant(nums, nums.size() - k, 0, nums.size() - 1);
        return nums[nums.size() - k];
    }
    
    int getRand(int start, int end){
        if(end < start) {
            return 0;
        }
        srand((unsigned)time(0));
        return rand()%(end-start+1) + start;
    }
    
    int swap(vector<int>& nums, int i, int j){
        int temp = nums[i];
        nums[i]=nums[j];
        nums[j]=temp;
    }
    
    void quickSortVariant(vector<int>& nums, int k, int start, int end){
        int flag = getRand(start, end); //找到一个标记元素
        swap(nums, start, flag);
        int flagNum = nums[start];
        int i=start, j=end;
        while(i<j){
            while(j>i&&nums[j]>=flagNum){
                j--;
            }
            nums[i]=nums[j];
            while(j>i&&nums[i]<=flagNum){
                i++;
            }
            nums[j]=nums[i];
        }
        nums[i]=flagNum;
        if(i>k){
            quickSortVariant(nums, k, start, i - 1);
        }else if(i<k){
            quickSortVariant(nums, k, i+1, end);
        }
    }
};

[LeetCode] Kth Largest Element in an Array

原文：http://blog.csdn.net/kangrydotnet/article/details/45973575