这个题目可以作为练习写大/小根堆的实现,不过貌似时间复杂度还是蛮高的。在洛谷上面一道模板题上面好像就超时了几个点,不知道是不是我实现的问题。那么除此之外,最容易想到的方法是先对该数组进行排序,然后取出第K或MAX-K数来。当选择使用快排的时候,时间复杂度是$O(nlogn)$。但还有一种更优的方法是利用快排划分出来的主元位置再递归寻找,这种方法叫作随机选择算法。它对任何输入都可以达到$O(n)$的期望时间复杂度。
1 #include <cstdlib> 2 #include <algorithm> 3 #include <cmath> 4 5 //随机选择主元 其实也是快排的一种写法 6 int randPartition(int A[],int left,int right) 7 { 8 // rand()/RAND_MAX得到一个0~1的小数再乘以相差值right-left最后加到left四舍五入得到随机值 9 int p = round(1.0*rand()/RAND_MAX*(right-left)+ left); 10 swap(A[p],A[left]); 11 int temp = A[left]; 12 while(left<right) // 跳出循环时left==right 13 { 14 while(left < right && A[right]>temp) 15 right--; 16 A[left] = A[right]; 17 while(left < right && A[left]<=temp) 18 left++; 19 A[right] = A[left]; 20 } 21 A[left] = temp; 22 return left; 23 } 24 25 //递归实现查询K值 26 int randSelect(int A[],int left,int right,int k) 27 { 28 if(left == right) 29 return A[left]; 30 int index = randPartition(A,left,right); 31 int M = index-left+1; // 表示从左到右第M个数 32 if(M==k) 33 return A[index]; 34 if(M<k) 35 randSelect(A,index+1,right,k-M); //注意 k-M 36 else if(M>k) 37 randSelect(A,left,index-1,k); 38 }