问题描述
Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
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大小的小顶堆，使这个小顶堆由当前最大的k个元素组成。
一篇关于堆的文章
- 堆的定义
大顶堆：每个节点的值都不大于其父节点的值；
小顶堆：每个节点的值都不小于其父节点的值。 - 堆的调整
对于某节点i，比较其与自身孩子节点2i+1、2i+2值的大小，决定是否调换，调换后要继续在新位置比较与新位置孩子节点值的大小，直到到达合适位置。 - 堆的建立
从最后一个非孩子节点开始，由后向前对每一个非孩子节点进行调整。
AC代码
class Solution(object):
def findKthLargest(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
self.build(nums, k)
for i in range(k, len(nums)):
if nums[i] > nums[0]:
nums[0] = nums[i]
self.adjust(nums, 0, k)
return nums[0]
def build(self, nums, k):
n = (k-2)/2
for i in range(n, -1, -1):
self.adjust(nums, i, k)
def adjust(self, nums, index, k):
i = index
while True:
index1 = 2 * i + 1
index2 = 2 * i + 2
if index1 >= k:
return
if index2 >= k:
if nums[i] > nums[index1]:
nums[i], nums[index1] = nums[index1], nums[i]
i = index1
else:
return
else:
index = index1 if nums[index1] < nums[index2] else index2
if nums[i] > nums[index]:
nums[i], nums[index] = nums[index], nums[i]
i = index
else:
return
Runtime: 68 ms, which beats 58.08% of Python submissions.
