Kth Largest Element in an Array

时间：2015-08-02 23:24:40 阅读：367 评论：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.

解题思路：

求一个未排序的数组的第k大的值，其中相同大小的仍然计算大小。并非是不同的第k大的值。

方法一：

我们将数组直接排序，第k大的值也就是下标为n-k的值，代码如下：

</pre><pre name="code" class="cpp">class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        if(nums.size()==0) return 0;
        if(nums.size()==1) return nums[0];
        sort(nums.begin(),nums.end());
        return nums[nums.size()-k];
    }
};

方法二：

我们借鉴快速排序的思想，将数组分成两部分，前部分小与key值，后部分大于key值，第k大的值就是第n-k+1小的值，也就是前半部分的大小为n-k+1的时候，我们的返回值就是此时的nums[n-k]值，此时前半部分的最大下标为n-k（下标从0开始的）。一旦找到前半部分满足如此条件，我们就直接返回nums[n-k],不用继续进行下面的排序工作，代码如下：

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
              if(nums.size()==0) return 0;
        if(nums.size()==1) return nums[0];
        int low=0,high=nums.size()-1;
        while(low<high)
        {
            int l=low;
            int h=high;
            int prio=nums[low];
            while(l<h)
            {  
                while(l<h&&nums[h]>prio) h--;
                      swap(nums[h],nums[l]);
                while(l<h&&nums[l]<=prio) l++;
                      swap(nums[h],nums[l]);
            }
            nums[l]=prio;
            if(l==nums.size()-k) return nums[nums.size()-k];
            else if(l>nums.size()-(k)) high=l-1;
            else
            low=l+1;
        }
        return nums[nums.size()-(k)];
    }
};

方法三：

同方法二类似，不同的是我们不用由小到大排序，我们从大到小排序，这样更直观。代码如下：

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        if(nums.size()==0) return 0;
        if(nums.size()==1) return nums[0];
        int low=0,high=nums.size()-1;
        while(low<high)
        {
            int l=low;
            int h=high;
            int prio=nums[low];
            while(l<h)
            {  
                while(l<h&&nums[h]<prio) h--;
                      swap(nums[h],nums[l]);
                while(l<h&&nums[l]>=prio) l++;
                      swap(nums[h],nums[l]);
                
            }
            nums[l]=prio;
            if(l==k-1) return nums[k-1];
            else if(l>k-1) high=l-1;
            else
            low=l+1;
        }
        return nums[k - 1];
    }
};

优缺点分析:

利用快排的思想，平均时间复杂度O(n)，4ms AC。

直接sort是O(n*log(n))

Kth Largest Element in an Array

原文：http://blog.csdn.net/sinat_24520925/article/details/47211225

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)