189 - 347 前k个高频元素

题目

给定一个非空的整数数组，返回其中出现频率前 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 是数组的大小。

解答

第一反应是用map，存一下所有数字出现的频率，然后输出最高的。。

看了题解发现，用hashmap存频率是无法避免的，关键是如何快速有效把高频元素取出来

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        from heapq import heappush
        from heapq import heappop
        hs = {}
        for num in nums:
            if num not in hs:
                hs[num] = 1
            else:
                hs[num] += 1
        heap = []
        for i in hs:
            heappush(heap, (-hs[i], i))
        ans = []
        for _ in range(k):
            p = heappop(heap)
            ans.append(p[1])
        return ans

Runtime: 108 ms, faster than 76.04% of Python3 online submissions for Top K Frequent Elements.

Memory Usage: 17.4 MB, less than 6.25% of Python3 online submissions for Top K Frequent Elements.

python：我有一个方法。。。

https://leetcode.com/problems/top-k-frequent-elements/discuss/81697/Python-O(n)-solution-without-sort-without-heap-without-quickselect

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        from collections import Counter
        most_common = Counter(nums).most_common()
        fin = []
        for l in range(0, k):
            fin.append(most_common[l][0])
        return fin

Runtime: 104 ms, faster than 88.26% of Python3 online submissions for Top K Frequent Elements.

Memory Usage: 17.2 MB, less than 6.25% of Python3 online submissions for Top K Frequent Elements.

还能更加简洁。。

https://leetcode-cn.com/problems/top-k-frequent-elements/solution/qian-k-ge-gao-pin-yuan-su-by-leetcode/

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        from collections import Counter
        from heapq import nlargest
        count = Counter(nums)
        return nlargest(k, count.keys(), key=count.get)

Runtime: 96 ms, faster than 98.80% of Python3 online submissions for Top K Frequent Elements.

Memory Usage: 17.1 MB, less than 6.25% of Python3 online submissions for Top K Frequent Elements.