347. 前 K 个高频元素 [medium]

https://leetcode-cn.com/problems/top-k-frequent-elements/

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

提示：

你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
你可以按任意顺序返回答案。

通过次数109,208提交次数177,125

Second Try

2020-10-06

看了题解，需要考虑n个元素都是独立的情况，因此first try中的复杂度可能出现O(nlgn)的情况，还是需要上优先队列。

使用最小堆保留数字，说是最小堆，其实保存的反而是最大的k个数字，因此每次超出数量的时候使用heappop弹出的都是最小值，剩下的k个都大于最小值。

最小堆复杂度为O(nlgk), 每次pop和push一个元素的复杂度都是O(lgk), 总共n个元素都需要过一遍。

看题解还可以使用快排，什么时候小于pivot的数值凑够了k就可以终止，并且每次pivot index都使用随机数，这样勉强也小于O(nlgn).

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        counter = collections.Counter(nums)
        
        heap = []
        for key, value in counter.items():
            heapq.heappush(heap, [value, key])
            if len(heap) > k:  # k 差点与 for k, v in counter.items()混淆
                heapq.heappop(heap)
        return [v for k, v in heap]

执行用时：56 ms, 在所有 Python3 提交中击败了52.25%的用户
内存消耗：16 MB, 在所有 Python3 提交中击败了93.86%的用户

First Try

2020-10-06

第一波统计数量是O(N), 第二波是O(KlgK), K是不同元素的数量，整体复杂度勉强小于O(nlgn).

不过如果只是这个级别，感觉也只是easy难度，而不是medium？

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        c = collections.Counter(nums)
        rv = sorted(c.items(), key = lambda x: x[1], reverse=True)[:k]
        return [k for k, v in rv] 
        

执行用时：56 ms, 在所有 Python3 提交中击败了52.25%的用户
内存消耗：16.1 MB, 在所有 Python3 提交中击败了75.17%的用户

347. 前 K 个高频元素 [medium]​

Second Try​

First Try​

347. 前 K 个高频元素 [medium]

Second Try

First Try