Top K问题，求最大的第K个数

leetcode 215

leetcode 215

此题大概几种思路， 伪代码实现：

1. 将n个数排序后，取最大的第k个数

sort(arr, 1, n);
return arr[k];

时间复杂度 O(nlogn)

2. 利用冒泡进行局部排序，每冒泡一次，得到最大值，冒第k次泡，得到最后结果

for(i=1 to k){
     bubble_find_max(arr,i);
}
return arr[k];

时间复杂度 O(n*k)

3. 借助小顶堆，堆顶元素为当前堆中最小的元素。然后扫描元素中如果大于堆顶元素，则替换，然后调整堆。最终堆顶元素即为第K大元素

heap[k] = make_heap(arr[1, k]);
for(i=k+1 to n){
     adjust_heap(heep[k],arr[i]);
}
return heap[0];

时间复杂度 O(n*logK)

4. 快速随机选择算法。利用分治思想，通过类似快排中的partition。 partition过程：首先随机选择一个pivot, 通过与数组元素两两比较，最终pivot左边均小于pivot, 右边均大于pivot。 此时如果pivot右边元素数量 num >= k, 则第k大元素一定在右边，递归此partition过程, 求[pivot+1, high] 的第k大 ; 否则如果num < k, 则递归求左边[low, pivot-1] 的第 k - num -1大。

int RS(arr, low, high, k){
  if(low== high) return arr[low];
  pivot = partition(arr, low, high);
  num = n-pivot; //数组后半部分元素个数
  if(num>=k)
      return RS(arr, pivot+1, high, k); //求后半部分第k大
  else
      return RS(arr, low, pivot-1, k-num-1); //求前半部分第k-num-i大
}

由于递归只会执行其中一个分支， 在pivot随机的情况下，平均时间复杂度为O(n)， 最坏情况下为O(n^2)

参考文章：
Top K 问题的最优解 - 快速选择算法（Quickselect）
拜托，面试别再问我TopK了