傳送門：215. 數(shù)組中的第K個(gè)最大元素浑吟。

在未排序的數(shù)組中找到第 k 個(gè)最大的元素履肃。請(qǐng)注意偏灿，你需要找的是數(shù)組排序后的第 k 個(gè)最大的元素星瘾，而不是第 k 個(gè)不同的元素走孽。

示例 1:

輸入: [3,2,1,5,6,4] 和 k = 2
輸出: 5

示例 2:

輸入: [3,2,3,1,2,4,5,5,6] 和 k = 4
輸出: 4

說明:

你可以假設(shè) k 總是有效的，且 1 ≤ k ≤ 數(shù)組的長(zhǎng)度琳状。

這道題應(yīng)該說是無比重要的高頻考題磕瓷，是一定要掌握的，兩種思路分別使用了很基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)（優(yōu)先隊(duì)列）和算法（partition）念逞。

解法1：使用快速排序 partition 的思路

Python 代碼：

class Solution:

    # 數(shù)組中的第 K 個(gè)最大元素
    # 數(shù)組中第 k 大的元素困食，它的索引是 len(nums) - k
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """

        left = 0
        right = len(nums) - 1

        while True:
            index = self.__partition(nums, left, right)
            if index == len(nums) - k:
                return nums[index]
            if index > len(nums) - k:
                right = index - 1
            else:
                left = index + 1

    def __partition(self, nums, left, right):
        """
        partition 是必須要會(huì)的子步驟，一定要非常熟練
        典型的例子就是：[3,7,8,1,2,4]
        遇到比第一個(gè)元素大的或等于的翎承，就放過硕盹，遇到小的，就交換
        在 [left,right] 這個(gè)區(qū)間執(zhí)行 partition
        :param nums:
        :param left:
        :param right:
        :return:
        """
        pivot = nums[left]
        k = left
        for index in range(left + 1, right + 1):
            if nums[index] < pivot:
                k += 1
                nums[k], nums[index] = nums[index], nums[k]
        nums[left], nums[k] = nums[k], nums[left]
        return k


if __name__ == '__main__':
    nums = [3, 7, 8, 1, 2, 4]
    solution = Solution()
    result = solution.findKthLargest(nums, 2)
    print(result)

解法2：使用優(yōu)先隊(duì)列

參考了：https://leetcode.com/problems/kth-largest-element-in-an-array/discuss/167837/Python-or-tm

Python 代碼：

import heapq

class Solution(object):
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        L = []
        for index in range(k):
            # 默認(rèn)是最小堆
            heapq.heappush(L, nums[index])
        for index in range(k, len(nums)):
            top = L[0]
            if nums[index] > top:
                # 看一看堆頂?shù)脑剡犊В灰榷秧斣卮蟠窭吞鎿Q堆頂元素
                heapq.heapreplace(L, nums[index])
        # 最后堆頂中的元素就是堆中最小的，整個(gè)數(shù)組中的第 k 大元素
        return L[0]


if __name__ == '__main__':
    nums = [3, 7, 8, 1, 2, 4]
    solution = Solution()
    result = solution.findKthLargest(nums, 2)
    print(result)

（本節(jié)完）