前K大的数

TOP K

从数组中找到最大的K的数

思路一：

将整个数组排序，使用快排，O(n*logn)

思路二：

K后面的元素排序无意义，可以去掉这个步骤。使用冒泡排序，每次选择最大的一个数浮上去，重复K次后，可以得到结果，O(n*k)

思路三：

K个元素的排序也无意义，使用堆排序。取出前k个元素，建立一个小顶堆，O(k)，然后遍历剩下的n-k个元素，每个元素进堆为O(logk)，整个复杂度为O(k) + O((n-k)logk) = O(nlogk)

思路四：

分治法核心思路是把大问题分解为小问题，然后分开解决，最终解决大问题。

减治法是把大问题分解为小问题，然后只解决其中一个分支，也可以解决大问题。比如二分查找，每次只需要查找某一边，复杂度为O(logn).

这个问题也可以用减治法，称为随机选择。

利用快排的dopivot函数，将数组分为以i为中心的左大右小部分（分解问题），判断i与k的大小，可以知道k在i的哪一边。多次循环可以分出以k为中心的左大右小区域。循环次数与k大小无关，dopivot函数复杂度为O(n)，所以整个随机选择的复杂度为O(n)