LeetCode: 347. 前 K 个高频元素 - Python_python 前k个元素

347. 前 K 个高频元素

问题描述：

给定一个n个数的数组（n <= 10,000,000），以及一个数字k，请输出：数组中出现最频繁的k个数。

例如：数组[2,3,1,5,2,1,2,4,3,2,3]， k=3 出现最频繁的数分别是2和3（2出现4次，3出现3次），其次是1（出
现2次） 所以输出1,2,3这3个数即可，输出顺序随意。

问题分析：

方法基本有两个：

（1）用hash统计出现次数，然后根据次数进行排序，输出结果即可。
（2）用hash统计出现次数，然后使用堆处理，输出结果即可。

Python3实现：

方法一： 使用排序

# @Time   :2019/01/31
# @Author :LiuYinxing
# hash 数组 排序


from collections import defaultdict


class Solution:
    def topKFrequent(self, A, k):
        counts = defaultdict(int)  # 所有值被初始化为0
        for x in A:  # 计数统计
            counts[x] += 1
        if len(counts) <= k:
            return list(counts.keys())

        res = sorted(counts.items(), key=lambda x:x[1], reverse=True)  # 排序输出
        return [x[0] for x in res[:k]]

if __name__ == '__main__':
    solu = Solution()
    A, k = [2, 3, 1, 5, 2, 1, 2, 4, 3, 2, 3], 10
    A, k = [2, 3, 1, 5, 2, 1, 2, 4, 3, 2, 3], 3
    print(solu.findFrequentlyK(A, k))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

方法二：使用堆（省事，使用Python自带）

# @Time   :2019/01/31
# @Author :LiuYinxing
# hash 数组 堆


from collections import defaultdict
import heapq

class Solution:
    def topKFrequent(self, A, k):
        counts = defaultdict(int)  # 所有值被初始化为0
        for x in A:  # 计数统计
            counts[x] += 1
        if len(counts) <= k:
            return list(counts.keys())

        res = heapq.nlargest(k, counts.items(), key=lambda x: x[1])  # 从堆中找出最大的K个数

        return [x[0] for x in res]


if __name__ == '__main__':
    solu = Solution()
    A, k = [2, 3, 1, 5, 2, 1, 2, 4, 3, 2, 3], 10
    A, k = [2, 3, 1, 5, 2, 1, 2, 4, 3, 2, 3], 3
    print(solu.findFrequentlyK(A, k))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

方法三

# 代码参考[2]
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = collections.Counter(nums)
        num_cnt = list(count.items())
        topKs = self.findTopK(num_cnt, k, 0, len(num_cnt) - 1)
        return [item[0] for item in topKs]
    
    def findTopK(self, num_cnt, k, low, high):
        pivot = random.randint(low, high)
        num_cnt[low], num_cnt[pivot] = num_cnt[pivot], num_cnt[low]
        base = num_cnt[low][1]
        i = low
        for j in range(low + 1, high + 1):
            if num_cnt[j][1] > base:
                num_cnt[i + 1], num_cnt[j] = num_cnt[j], num_cnt[i + 1]
                i += 1
        num_cnt[low], num_cnt[i] = num_cnt[i], num_cnt[low]
        if i == k - 1:
            return num_cnt[:k]
        elif i > k - 1:
            return self.findTopK(num_cnt, k, low, i - 1)
        else:
            return self.findTopK(num_cnt, k, i + 1, high)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

声明： 总结学习，有问题或不当之处，可以批评指正哦，谢谢。

[1] 题目链接 LeetCode:47. 前 K 个高频元素
[2] 优秀代码参考 LeetCode解题社区链接
[3] 题目链接: 2019/01/31 在线笔试题