[LeetCode] 215. Kth Largest Element in an Array_Medium tag: Array, Heap

Given an integer array nums and an integer k, return the kth largest element in the array.

Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:

Input: nums = [3,2,1,5,6,4], k = 2
Output: 5

Example 2:

Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4

Constraints:

• 1 <= k <= nums.length <= 104
• -104 <= nums[i] <= 104

Ideas:

1. sort   T: O(n * lgn)    S: O(1)

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        nums.sort()
        return nums[len(nums) - k]

2. 利用heap, 维持一个size为k的heap，每次insert都是lgk的时间，所以T: O(n * lgk)    S: O(k)

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        return heapq.nlargest(k, nums)[-1]

3. 利用quicksort的思想来快速sort， 这样来关心最后n - k 的sort的顺序。只要保证n - k的数在相应的位置上即可，不用担心n- k 前面的数到底是不是sort了。

参考quickSort use two pointers to decrease Time into O(n * lgn ) or O(n)

TODO: 

[LeetCode] 215. Kth Largest Element in an Array_Medium tag: Array, Heap

原文：https://www.cnblogs.com/Johnsonxiong/p/14943022.html