问题描述

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.