首页 > 其他 > 详细

Leetcode[215]-Kth Largest Element in an Array

时间:2015-06-14 09:33:47      阅读:128      评论: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.

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.


法一:使用STL的sort排序O(NlogN)

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

法二:自己写快速排序O(NlogN)

int findKthLargest(vector<int>& nums, int k){

    quickSort(nums, 0 ,nums.size());
    return nums[nums.size()-k];

}
void quickSort(vector<int> &nums, int left, int right){
    int i = left, j = right - 1;
    if(i < j){
        int po = nums[i];
        while(i < j){
            while(i < j && nums[j] >= po) j--;
            if(i < j) {
                nums[i++] = nums[j];
            }
            while(i < j && nums[i] <= po ) i++;
            if(i < j){
                nums[j--] = nums[i];
            }
        }
        nums[i] = po;
        quickSort(nums, left, i);
        quickSort(nums, i+1, right);

    }
}

法三:使用建堆法 时间复杂度O(klogN)

int findKthLargest(vector<int>& nums, int k){
    make_heap(nums.begin(), nums.end());
    for(auto i=0; i<k-1;i++){
        pop_heap(nums.begin(), nums.end());
        nums.pop_back();
    }
    return nums.front();
}

方法四:此方法是论坛看到的,O(N)

int findKthLargest(vector<int>& nums, int k){
     int i, m, n, pivot, head =0, tail = nums.size()-1, maxV;

    while(1){
        m = head, n= tail;
        pivot = nums[m++];
        while(m <= n) {
            if(nums[m] >= pivot) m++;
            else if(nums[n] < pivot) n--;
            else {
                swap(nums[m++], nums[n--]);
            }
        }
        if(m-head == k) 
            return pivot;
        else if(m-head < k) {
            k -= (m-head); 
            head = m;  
        }
        else {
            tail = m-1;
            head = head+1;
        }
    }

}

Leetcode[215]-Kth Largest Element in an Array

原文:http://blog.csdn.net/dream_angel_z/article/details/46484539

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!