跳到主要内容

215. 数组中的第K个最大元素 [medium]

215. 数组中的第K个最大元素 [medium]​

https://leetcode-cn.com/problems/kth-largest-element-in-an-array/

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

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

示例 2:

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

说明:

你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

通过次数169,384 | 提交次数262,740

Second Try​

2020-10-06

已经完全不记得做过这题了，做了347后顺手再做这题目，直接用最小堆存储最大的前k个数值。其实复杂度比first try中用默认sorted要小的，但执行时间就太多波动因素了。

复杂度为O(nlgk)，而非O(nlgn)

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        # 仍然使用最小堆，保存的是k个最大的元素
        heap = []
        for n in nums:
            heapq.heappush(heap, n)
            if len(heap) > k:
                heapq.heappop(heap)
        return heap[0]
  • 执行用时：56 ms, 在所有 Python3 提交中击败了49.92%的用户
  • 内存消耗：14 MB, 在所有 Python3 提交中击败了48.39%的用户

First Try​

2020-07-16

直接排序取k，一行带过。但看题解，这题目的意思是要自己实现快排，或者实现极大堆。

快排的时候有两个优化，其一是对数组进行随机化，避免成为O(N^2)的算法；其二是只要考虑pivot点的排序即可，不需要对pivot的左右两边都排序，当确认了位置为k的pivot点就可以直接返回了。

极大堆在学算法4的时候用java写过，虽然python还没练过手，但至少知道是怎么回事，先不花费时间了。

class Solution(object):
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        # 不太懂啊，直接排序取k不行吗？
        return sorted(nums, reverse=True)[k - 1]
  • 执行用时：28 ms, 在所有 Python 提交中击败了70.81%的用户
  • 内存消耗：13.1 MB, 在所有 Python 提交中击败了16.67%的用户