leetcode 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 是数组的大小。

题解

统计相同数字出现的次数,然后根据出现次数存入二维数组中,最后从二维数组的后面开始取出高频数值

示例代码(go)

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
func topKFrequent(nums []int, k int) []int {
arr := make([]int, 0)
if len(nums) == 0 {
return arr
}
m := make(map[int]int)
maxCount := 0
for _,v := range nums {
m[v] += 1
if m[v] > maxCount {
maxCount = m[v]
}
}
tmp := make([][]int, maxCount+1)
for k,v := range m {
tmp[v] = append(tmp[v], k)
}
for i := maxCount; i >= 0; i-- {
if len(tmp[i]) == 0 {
continue
}
arr = append(arr, tmp[i]...)
if len(arr) == k {
break
}
}
return arr
}