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

题目

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

示例

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

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/top-k-frequent-elements
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

  1. 若想得出某个数出现的次数,并进行一一对应的存储,可以使用map,因此用map[int]int数据结构计算出key-value
  2. 由于map遍历是无序的,根据题目必须根据次数求出key,存储到数组中 。且遍历次数 的时候如果是有序的,就可以倒序遍历,得出相应的k个数。
  3. 由上述特性,可以设置若干个桶,桶的下标代表频率,即第i桶中装的是频率为2的数字;
  4. 比如第一个示例,可以计算出:
    1
    2
    3
    4
    5
    6
    buckets = {
    {},//频率为 0
    {3},//频率为 1
    {2},//频率为 2
    {1},//频率为 3
    }
  1. 遍历这个桶 ,同时限制最终数组保证为k的大小 ,假如遍历第i个桶时,桶中的长度大于 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
27
28
29
30
31
32
33
34
35
36
37
38
39
func topKFrequent(nums []int, k int) []int {
//存储值和次数的对应关系
m :=make(map[int]int,len(nums))
for _,v :=range nums{
if _,ok :=m[v];ok{
m[v]++
}else{
m[v] = 1
}
}
// 定义一个数组表示桶,+1是为了表示第i个桶表示频率为i
burkets :=make([][]int,len(nums)+1)
for k,v :=range m{
//追加对应的值
burkets[v] = append(burkets[v],k)
}
// fmt.Println(burkets)
//最终结果集
result :=[]int{}
for j :=len(burkets)-1;j>=0 && len(result) < k;j--{
//桶中没有数据时直接跳过
if len(burkets) == 0{
continue
}
//桶中数的长度小于需要添加的长度
if len(burkets[j])<=(k-len(result)){
for _,va :=range burkets[j]{
result = append(result,va)
}
}else{
//当桶中数大于需要追加的长度 ,进行截取
burkets[j] = burkets[j][0:k-len(result)]
for _,va :=range burkets[j]{
result = append(result,va)
}
}
}
return result
}