寻找第k个最大数 C++

题目描述
有一个整数数组，请你根据快速排序的思路，找出数组中第K大的数。

给定一个整数数组a,同时给定它的大小n和要找的K(K在1到n之间)，请返回第K大的数，保证答案存在。

1.暴力法

class Finder {
public:int findKth(vector<int> a, int n, int K) {// write code heresort(begin(a),end(a));return a[n-K];}

2.快排法

class Finder {
public:int findKth(vector<int> a, int n, int K) {// write code herereturn quickSortK(a,0,n-1,K);}int quickSortK(vector<int>&nums,int start,int end,int K){int index=partition(nums,start,end);if(index==K-1) return nums[index];if(index<K-1) return quickSortK(nums,index+1,end,K);return quickSortK(nums,start,index-1,K);}int partition(vector<int>&nums,int start,int end){//引用传递int k=rand()%(end-start+1)+start;//随机数增速swap(nums[k],nums[end]);int i=start-1;for(int j=start;j<end;j++){if(nums[j]>=nums[end]){swap(nums[++i],nums[j]);}}i++;swap(nums[i],nums[end]);return i;}
};

3.堆排序法
1.自下向上构建最大堆，构建完成后堆顶为最大值
2.循环操作：删除堆顶并重新堆排序，删除操作执行K-1次后堆顶即为所求值

class Finder {
public:int findKth(vector<int> a, int n, int K) {// write code hereint Size=a.size();buildHeap(a,Size);while(--K){swap(a[0],a[Size-1]);Size--;maxheap(a,0,Size);}return a[0];}void maxheap(vector<int>&a,int i,int Size){int l=2*i+1,r=2*i+2;int largest=i;if(l<Size&&a[l]>a[largest])largest=l;if(r<Size&&a[r]>a[largest])largest=r;if(largest!=i){swap(a[i],a[largest]);maxheap(a,largest,Size);}}void buildHeap(vector<int>&a,int Size){for(int i=Size/2;i>=0;i--){maxheap(a,i,Size);}}
};

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！