Leetcode 347.前k个高频元素

1.题目描述

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

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

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

提示：

• 1 <= nums.length <= 105
• k 的取值范围是 [1, 数组中不相同的元素的个数]
• 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

2.思路分析

2.1 堆

首先遍历整个数组，并使用哈希表记录每个数字出现的次数，并形成一个「出现次数数组」。找出原

数组的前 k 个高频元素，就相当于找出「出现次数数组」的前 k 大的值。

可以利用堆的思想：建立一个小顶堆，然后遍历「出现次数数组」：

• 如果堆的元素个数小于 k，就可以直接插入堆中。

• 如果堆的元素个数等于 k，则检查堆顶与当前出现次数的大小。如果堆顶更大，说明至少有 k 个

  数字的出现次数比当前值大，故舍弃当前值；否则，就弹出堆顶，并将当前值插入堆中。

遍历完成后，堆中的元素就代表了「出现次数数组」中前 k大的值。

3.代码实现

3.1 堆

import heapq
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # 优先级队列:披着外衣的堆
        # 1.统计元素出现的次数(map: key->nums[i] value:count)
        map_ = dict()
        for i in range(len(nums)):
            map_[nums[i]] = map_.get(nums[i],0)+1
        
        # 2.对频率进行排序(构建小顶堆)
        pri_que = []

        #用固定大小为k的小顶堆,扫描所有频率的数值,若堆的大小>k,则堆顶元素弹出
        for key,freq in map_.items():
            heapq.heappush(pri_que,(freq,key))
            if len(pri_que) > k:
                heapq.heappop(pri_que)
       
        # 3.找出前k个高频元素
        result = [0] * k
        for i in range(len(pri_que))[::-1]:
            result[i] = heapq.heappop(pri_que)[1]
        
        return result
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

复杂度分析

• 时间复杂度：O(Nlogk)，其中 N 为数组的长度。我们首先遍历原数组，并使用哈希表记录出现次数，每个元素需要 O(1) 的时间，共需O(N) 的时间。随后，我们遍历「出现次数数组」，由于堆的大小至多为 k，因此每次堆操作需要 O(logk) 的时间，共需 O(Nlogk) 的时间。二者之和为O(Nlogk)。
• 空间复杂度：O(N)。哈希表的大小为 O(N)，而堆的大小为 O(k)，共计为 O(N)。

3.2 朴素的方法

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # 朴素的方法
        #1.统计每个元素出现的频率
        dic = defaultdict(int)
        for item in nums:
            dic[item] += 1
        # defaultdict(, {1: 3, 2: 2, 3: 1})
        #2.取出前k个频率很高的元素(排序)
        # sorted(iterable, cmp=None, key=None, reverse=False)
        freq_items = sorted(dic.items(),key=lambda x:x[1])[-k:]
        return [item[0] for item in freq_items]
1
2
3
4
5
6
7
8
9
10
11
12