Leetcode 第K大元素

元素"/>

Leetcode 第K大元素

题目：

• 在数组中找到第 k 大的元素。
• 要求时间复杂度为O(n)，空间复杂度为O(1)。

输入：
n = 1, nums = [1,3,4,2]
输出：
4

分析：

最开始想到是利用快排序。快速排序在每一次swap之后都能够找到某一个元素（例如 a a a)正确的位置。则：

• a a a刚好是第K个元素，则输出；
• 若 a a a的位置在第K个位置右侧，则接下来去其左侧快排；
• 若 a a a的位置在第K个位置左侧，则接下来去其右侧快排；

代码：

class Solution {
public:/*** @param n: An integer* @param nums: An array* @return: the Kth largest element*/int kthLargestElement(int n, vector<int> &nums) {// write your code herereturn getRes(nums,n,0,nums.size()-1);}int getRes(vector<int> &nums,int k,int left, int right){int tmp=nums[left],n=nums.size(),tleft=left,tright=right;while(left<right){while(right>left&&nums[right]>tmp) right--;if(right>left){nums[left++]=nums[right];}while(left<right&&nums[left]<=tmp) left++;if(left<right) nums[right--]=nums[left];}nums[left]=tmp;if(left==n-k) return tmp;else if(left<n-k) return getRes(nums,k,left+1,tright);else return getRes(nums,k,tleft,left-1);}
};

后来搜到了各种神奇的解决方法：

参考 沧海漂游_的文章：
方法2：利用STL模板库中的算法：nth_element

• 通过调用nth_element(start, start+n, end) 方法可以使第n大元素处于第n位置（从0开始,其位置是下标为 n的元素），并且比这个元素小的元素都排在这个元素之前，比这个元素大的元素都排在这个元素之后，但不能保证他们是有序的。注意，题目中是第K个最大的元素，又因为下标从0开始，则 start+n = end -k ，此时，start+n （end -k）就是 第K大的元素。

class Solution {
public:/*** @param n: An integer* @param nums: An array* @return: the Kth largest element*/int kthLargestElement(int n, vector<int> &nums) {// write your code herenth_element(nums.begin(),nums.end()-n,nums.end());return *(nums.end()-n);}
};

方法3,
放松时间复杂度的要求，利用中的sort(start,end) ，将数组/vector排序，然后输出第k大的数。

class Solution {
public:/*** @param n: An integer* @param nums: An array* @return: the Kth largest element*/int kthLargestElement(int n, vector<int> &nums) {// write your code heresort(nums.begin(),nums.end());return *(nums.end()-n);}
};

方法4：

• 如果要求原始数组不能修改，同时要求只能使用常数空间复杂度，那么上述方法就全都不能用了。考虑用二进制解法。比如对于int型正整数，4字节，即32位，如果第i位 置1，保持前i-1位不变，那么根据前i位可以将数组分成两部分，即可以起到二分的作用

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {int left=0,right=0,last=0,cur=0,mask=1;     //数组划分两部分，left保存较小部分元素个数，right保存较大部分元素个数int i,j;//处理负数，负数最高位为1,正数为0，用以确定last起始值。for(auto &m:nums){if(((1<<31)&m)!=0) left+=1;else right+=1;}if(right<k){last=1;k=k-right;}for(i=31;i>0;i--){cur=mask<<i;left=0,right=0;for(j=0;j<nums.size();j++){if(((last<<i)^(cur&nums[j]))==0){   //用来判断当前元素是否需要考虑if(((1<<(i-1))&nums[j])>0)  right+=1;else    left+=1;}}//跳出循环条件，如果k=1,且较大部分刚好只有一个元素，即为所求，或者较大部分无元素，而较小部分只有一个元素，即为所求if(right==1&&k==1){last=last<<i;last=last|(1<<(i-1));cur=cur|(1<<(i-1));break;}else if(k==1&&left==1&&right==0){last=last<<i;cur=cur|(1<<(i-1));break;}last=last<<1;if(right<k) k=k-right;  //由于考虑第K大，所有较大部分抛弃，K中需要减去对应的个数else    last=last|1;mask=(mask<<1)|1;}if(i==0) return last;   //如果32位全部考虑，那么此时last的值即为所求for(auto &m:nums){if((last^(cur&m))==0) return m;}return last>>1;}
};
//--------------------- 
//作者：沧海漂游_ 
//来源：CSDN 
//原文： 
//版权声明：本文为博主原创文章，转载请附上博文链接！方法5：二分查找
```cpp
class Solution {
public:int findKthLargest(vector<int>& nums, int k) {int left=nums[0],right=nums[0];for(auto it=nums.begin();it!=nums.end();it++){left=min(left,*it);right=max(right,*it);}int mid=(left+right)/2,count=0,flag=0,last=-1;while(count!=k){count=0,flag=0;mid=(left+right)/2;for(int i=0;i<nums.size();i++){if(mid==nums[i]) flag=1;if(nums[i]>=mid) count+=1;}if(count>k) left=mid+1;else if(count<k) right=mid-1;if(last==count) break;else last=count;}if(flag==1&&count==k) return mid;else if(count>k&&left==right-1) return right;else{int res=right;for(int i=0;i<nums.size();i++){if(nums[i]>mid){res=min(res,nums[i]);}}return res;}}
};
//--------------------- 
//作者：沧海漂游_ 
//来源：CSDN 
//原文： 
//版权声明：本文为博主原创文章，转载请附上博文链接！