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.
链接
STL自带排序,先排序后选定num.size()-k各元素即可
class Solution { public: int findKthLargest(vector<int>& nums, int k) { sort(nums.begin(),nums.end()); return nums[nums.size()-k]; } };快排的思想,不断进行Partition操作,选定pivot后,在pivot左侧找到第一个比pivot小的元素,pivot右侧找到第一个比pivot大的元素进行交换,同时移动左右指针,进行下一次循环,直到两者交叉为止。最后交换pivot与最右侧的元素
对于每次partition的返回值
如果找到的位置r在k-1左侧,则在r的右侧继续进行partition如果找到的位置r在k-1右侧,则在r的左侧继续进行partition找到的位置刚好是k-1,直接返回即第K大的元素 class Solution { public: int findKthLargest(vector<int>& nums, int k) { int left=0,right=nums.size()-1; while(true){ int r=Partition(nums,left,right); if(r<k-1) left=r+1; if(r==k-1) return nums[r]; if(r>k-1) right=r-1; } } protected: int Partition(vector<int>& nums,int left,int right){ int pivot=nums[left],i=left+1,j=right; while(i<=j){ if(nums[i]<pivot && nums[j]>pivot) swap(nums[i++],nums[j--]); if(nums[i]>=pivot) i++; if(nums[j]<=pivot) j--; } swap(nums[left],nums[j]); return j; } };堆排序的方法,先建立大顶堆,将堆顶元素与末尾元素交换再进行调整,执行K次后最后一个元素即第k大的元素。
class Solution { int left(int idx){ return (idx<<1)+1; } int right(int idx){ return (idx<<1)+2; } public: int findKthLargest(vector<int>& nums, int k) { buildMaxHeap(nums); for(int i=k;k>=1;k--){ swap(nums[0],nums[heap_size-1]); heap_size--; maxHeapfy(nums,0); } return nums[heap_size]; } void maxHeapfy(vector<int>& nums,int idx){ int maxtmp=idx; int l=left(idx),r=right(idx); if(l<heap_size&&nums[l]>nums[maxtmp]) maxtmp=l; if(r<heap_size&&nums[r]>nums[maxtmp]) maxtmp=r; if(idx!=maxtmp){ swap(nums[idx],nums[maxtmp]); maxHeapfy(nums,maxtmp); } } void buildMaxHeap(vector<int>& nums){ heap_size=nums.size(); for(int i=(nums.size()>>1)-1;i>=0;i--){ maxHeapfy(nums,i); } } private: int heap_size; };