题目:给定一个无序序列和一个数k,求这个无序序列中第K大的数
分析:
方案一:最朴素的方法利用快速排序然后找到第k个数,时间复杂度O(nlogn)
方案二:根据快速排序中的partition方法,每次可以把一个序列分成两个部分,左边全部小于等于基准,右边的全部大于等于基准。如果partition方法中基准的位置刚好是第k个则可以直接得多这个数,如果大于k说明在左边,如果小于k说明在右边。
利用这个方法每次可以将序列不断的划分直至找到这第k个数, 因为partition函数的时间复杂度最大为O(n),而我们每次都可以把序列分成一半,因此总的时间复杂度还是O(n)。
时间复杂度的证明:
1. 假设总的元素个数有n个,则
第一次枚举n个数
第二次枚举n/2
第三次枚举n/4
...................1
2. 则总的时间为n+n/2+n/4+....+1 <= 2n,因此时间复杂度为O(n)
举例:
例如无序序列为0 9 -1 6 7 3 5,k为3则第k大的数为6。
实例代码:
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; //Partition方法 int Partition(int *arrNum, int l, int r){ //不合法数据 if(arrNum == NULL || l > r){ return -1; } int mid = (l+r)>>1; swap(arrNum[mid], arrNum[r]); int leftSeqIndex = l; //枚举区间 for(int i = l; i < r; i++){ if(arrNum[i] < arrNum[r]){ if(i > leftSeqIndex){ swap(arrNum[i], arrNum[leftSeqIndex]); } ++leftSeqIndex; } } //基准交换回来 swap(arrNum[leftSeqIndex], arrNum[r]); return leftSeqIndex; } //求第k大的数 int GetNumber(int *arrNum, int n, int k){ //输出-1表示不合法 if(arrNum == NULL || n <= 0 || k <= 0 || k > n){ return -1; } //第k大的数等价于找第n-k+1小的数 k = n-k+1; int l = 0; int r = n-1; while(l <= r){ int index = Partition(arrNum, l, r); if(index+1 == k){ //找到 return arrNum[index]; } else if(index+1 < k){ //在右边序列找 l = index+1; } else{ //在左边序列找 r = index-1; } } } int main(){ int arrNum[] = {0,9,-1,6,7,3,5}; int value = GetNumber(arrNum, 7, 3); if(value == -1){ cout<<"no found number"; } else{ cout<<value<<endl; } getchar(); return 0; } /* 输出 6 */