class Solution {
public:
int partation(int l,vector<int> & a,int r){
int temp = a[r];
int k=l;
for(int i=l;i<r;i++){
if(a[i]>=temp){
swap(a[i],a[k++]);
}
}
swap(a[k],a[r]);
return k;
}
int findKthLargest(vector<int>& nums, int k) {
int pivot;
int l=0;
int r=nums.size()-1;
while(l<=r){
pivot = partation(l,nums,r);
if(pivot==k-1) break;
else if(pivot<k-1){
l = pivot+1;
}
else r=pivot-1;
}
if(l<=r) return nums[pivot];
return nums[pivot];
}
};
image
每次经过划分，如果中间值等于 K ，那么其左边的数就是 Top K 的数据；
当然，如果不等于，只要递归处理左边或者右边的数即可
该方法的时间复杂度是 O(n) ，简单分析就是第一次划分时遍历数组需要花费 n，而往后每一次都折半（当然不是准确地折半），粗略地计算就是 n + n/2 + n/4 +... < 2n，因此显然时间复杂度是 O(n)
对比第一个方法显然快了不少，随着数据量的增大，两个方法的时间差距会越来越大.
面对海量数据，我们就可以放分布式的方向去思考了
我们可以将数据分散在多台机器中，然后每台机器并行计算各自的 TopK 数据，最后汇总，再计算得到最终的 TopK 数据
这种数据分片的分布式思想在面试中非常值得一提，在实际项目中也十分常见
