Appearance
347. 前 K 个高频元素
题目描述
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1：
输入：nums = [1,1,1,2,2,3], k = 2
输出：[1,2]
示例 2：
输入：nums = [1], k = 1
输出：[1]
示例 3：
输入：nums = [1,2,1,2,1,2,3,1,3,2], k = 2
输出：[1,2]
提示：
1 <= nums.length <= 105
-104 <= nums[i] <= 104
- `k` 的取值范围是 `[1, 数组中不相同的元素的个数]`
- 题目数据保证答案唯一，换句话说，数组中前 `k` 个高频元素的集合是唯一的
**进阶：*你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n *是数组大小。
难度： Medium
题解代码
javascript
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
// hash + 桶
var topKFrequent = function(nums, k) {
const map = new Map()
nums.forEach(item => {
map.set(item, map.has(item) ? map.get(item) + 1 : 1)
})
if (k === map.size) return [...map.keys()]
const arr = [], res = []
map.forEach((v, k) => {
if (!arr[v]) arr[v] = [k]
else arr[v].push(k)
})
// console.log(arr)
for (let i = arr.length - 1; i >= 0, res.length < k; i--) {
if (arr[i]) {
res.push(...arr[i])
}
}
return res
};
// 堆
var topKFrequent = function (nums, k) {
const map = new Map()
nums.forEach(num => {
map.set(num, map.has(num) ? map.get(num) + 1 : 1)
})
const heap = []
let len = 0
map.forEach((val, key) => {
if (len < k) {
heap.push(key)
if (len === k - 1) {
// 构建最小堆 利用map做的映射
for (let i = Math.floor(k / 2); i >= 0; i--) {
heapify(map, heap, k, i)
}
}
} else {
if (map.get(heap[0]) < val) {
heap[0] = key
heapify(map, heap, k, 0)
}
}
len++
})
return heap
}
function heapify (map, heap, size, i) {
const l = i * 2 + 1
const r = i * 2 + 2
let min = i
if (l < size && map.get(heap[l]) < map.get(heap[min])) {
min = l
}
if (r < size && map.get(heap[r]) < map.get(heap[min])) {
min = r
}
if (min !== i) {
;[heap[i], heap[min]] = [heap[min], heap[i]]
heapify(map, heap, size, min)
}
}