Kth Largest Element in an Array
描述
Find the k-th largest element in an unsorted array.
For example, given [3,2,1,5,6,4] and k = 2, return 5.
Note:
You may assume k is always valid, 1 ≤ k ≤ array's length.
分析
这题是一道很好的面试题目，
- 题目短小，很快就能说清题意
- 有很多种解法。从简单到复杂的解法都有，梯度均匀。
- 不需要预先知道特殊领域知识。
这题有很多思路：
- 按从大到小全排序，然后取第
k个元素，时间复杂度O(nlogn)，空间复杂度O(1) - 利用堆进行部分排序。维护一个大根堆，将数组元素全部压入堆，然后弹出
k次，第k个就是答案。时间复杂度O(klogn)，空间复杂度O(n) - 选择排序，第
k次选择后即可得到第k大的数，时间复杂度O(nk)，空间复杂度O(1) - 堆排序，维护一个
k大小的小根堆，将数组中的每个元素与堆顶元素进行比较，如果比堆顶元素大，则删除堆顶元素并添加该元素，如果比堆顶元素小，则什么也不做，继续下一个元素。时间复杂度O(nlogk)，空间复杂度O(k)。 利用快速排序中的partition思想，从数组中随机选择一个元素x，把数组划分为前后两部分
sa和sb，sa中的元素小于x，sb中的元素大于或等于x。这时有两种情况：sa的元素个数小于k，则递归求解sb中的第k-|sa|大的元素sa的元素个数大于或等于k，则递归求解sa中的第k大的元素时间复杂度
O(n)，空间复杂度O(1)
思路4和5比较高效，可以接受，其他思路太慢了，不采纳。