题目描述
找出数组中第k大的数。
假设k是有效的，即 1 ≤ k ≤ 数组长度。
例子
Example 1: Input: [3,2,1,5,6,4] and k = 2 Output: 5
Example 2: Input: [3,2,3,1,2,4,5,5,6] and k = 4 Output: 4
思想 直接排序，然后取出第k大的数 - 时间复杂度O(nlogn)
(法1 - 快速选择) 快排的思想，每次选定一个基准数，然后将比基准数小的数移到左边，比基准数大的数移到右边... 每次都只考虑一半，直到找到第k个。
[时间复杂度] 我们采用随机选取的pivot，所以平均来看每次pivot都选在中间位置。T(n) = O(n + n/2 + n/4 + ... + 2 + 1) = O(2n) = O(n)。 类似于快排，最好O(n)，最差O(n^2)，平均O(nlogn).
(法2 - 堆排序) 首先建k个元素的小顶堆（堆顶元素最小），时间复杂度O(klogk)。然后，剩余的(n-k)个元素依次与堆顶元素x比较，大于x则替换，小于x则忽略；更新堆O(logk)。最后取堆顶元素，即为第k大的数。 总时间复杂度O(klogk+(n-k)logk) = O(nlogk)
解法1 快速选择。复杂度：时间O(n)，空间O(1)
from random import randint
class Solution(object):
def findKthLargest(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
pos = self.quickSort(nums, 0, len(nums)-1)
while pos != len(nums)-k:
if pos > len(nums)-k:
pos = self.quickSort(nums, 0, pos-1)
else:
pos = self.quickSort(nums, pos+1, len(nums)-1)
return nums[pos]
def quickSort(self, nums, left, right):
pivot = randint(left, right)
# 把基准数放到最后
number = nums[pivot]
nums[pivot], nums[right] = nums[right], nums[pivot]
# 初始化pos, 指向第一个≥基准数的位置
pos = left
for i in range(left, right):
if nums[i] < number:
nums[pos], nums[i] = nums[i], nums[pos]
pos += 1
nums[pos], nums[right] = nums[right], nums[pos]
return pos解法2 堆排序。复杂度：时间O(nlogk)，空间O(k)
import heapq
class Solution(object):
def findKthLargest(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
minHeap = [float('-inf')] * k
for num in nums:
if num > minHeap[0]:
heapq.heappop(minHeap)
heapq.heappush(minHeap, num)
return minHeap[0]