[python 刷题] 347 Top K Frequent Elements

[python 刷题] 347 Top K Frequent Elements

题目：

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

一般来说看到 any order 可以默认这题跟 dict/map/set 有关，这题的话依旧是用 dict 存储数字和出现的频率，随后根据 dict 中值进行排序，获取 top k 的数字。

在最差情况下，这个算法的时间复杂度为 $O(nlog(n))$——就是排序的耗时，解法如下：

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        map = {}

        for num in nums:
            map[num] = map.get(num, 0) + 1

        sorted_map = sorted(map.items(), key=lambda x: x[1], reverse=True)
        res = []

        for i in range(k):
            res.append(sorted_map[i][0])

        return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

sorted() 这个函数的语法为：sorted(iterable, key=key, reverse=reverse)，iterable 比较简单，key 的话排序的依据，默认为 None，reverse 也比较直接。

lambda 在 python 中就是一个比较方便创建小型匿名函数的方法。

这个案例中，使用 sorted_map = sorted(map.items(), key=lambda x: -x[1]，得出的结果也一样。

sorted() 会返回一个数组，不过在 dict 的情况下，返回的是 tuples 的数组，以 [1,1,1,2,2,3] 为例：

• map 的结果为 {1: 3, 2: 2, 3: 1}，即数字与频率的键值对
• sorted_map 的结果为 [(1, 3), (2, 2), (3, 1)]，即频率与出现的数字的 tuple

个人觉得 python 的各种函数是真的很方便……

另一个更加优化的写法是：

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = {}
        freq = [[] for i in range(len(nums) + 1)]

        for n in nums:
            count[n] = 1 + count.get(n, 0)
        for n, c in count.items():
            freq[c].append(n)

        res = []
        for i in range(len(freq) - 1, 0, -1):
            for n in freq[i]:
                res.append(n)
                if len(res) == k:
                    return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

这个写法的优势在于时间复杂度为 $O(n)$，依旧以 [1,1,1,2,2,3] 为例，最后 freq 的值为 [[], [3], [2], [1]]，下标(index) 对应数字出现的频率。这也就是为什么初始化的时候，freq 的大小为 len(nums) + 1

这个解法肯定是更优的，最差情况下二者的时间复杂度都为 $O(n)$，但是这里的空间复杂度就少了一个 $log(n)$