347. 前 K 个高频元素 🟨
题目
LeetCode 中等
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1：
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2：
输入: nums = [1], k = 1
输出: [1]
题解
方法：sort
- 时间复杂度：O(nlogn)
- 空间复杂度：O(map 的长度)
js
function topKFrequent(nums, k) {
// 统计出现次数
const map = new Map()
const len = nums.length
for (let i = 0; i < len; i++) {
const val = nums[i]
map.set(val, (map.get(val) || 0) + 1)
}
console.log(map)
// 对次数进行排序然后输出前 k 个
return [...map.entries()]
.sort((a, b) => b[1] - a[1])
.slice(0, k)
.map(a => a[0])
}
const nums = [1, 1, 1, 2, 2, 3],
k = 2
console.log('🌰', topKFrequent(nums, k)){}
🌰 [1,2]方法：堆排序
- 时间复杂度：O(nlogk)
- 空间复杂度：O(n)
js
function topKFrequentHeap(nums, k) {
//计算次数
let nlen = nums.length
const map = new Map()
for (let i = 0; i < nlen; i++) {
const val = nums[i]
map.set(val, (map.get(val) || 0) + 1)
}
console.log(map)
//以map建堆
const list = [...map.entries()]
let heapSize = list.length
let llen = list.length
buildMaxHeap(list, heapSize)
console.log(
'init maxHeap',
list.map(a => a.toString()),
)
//把堆顶下沉，并重新调整堆，一步步重复
for (let i = llen - 1; i >= llen - k; i--) {
swap(list, 0, i)
--heapSize
maxHeapify(list, 0, heapSize)
console.log(
i,
list.map(a => a.toString()),
)
}
return list.slice(-k).map(a => a[0])
// 自下而上构建一颗大顶堆
function buildMaxHeap(list, heapSize) {
for (let i = Math.floor(heapSize / 2) - 1; i >= 0; i--) {
maxHeapify(list, i, heapSize)
}
}
// 从左向右，自上而下的调整节点
function maxHeapify(list, i, heapSize) {
let l = i * 2 + 1
let r = i * 2 + 2
let largest = i
if (l < heapSize && list[l][1] > list[largest][1]) {
largest = l
}
if (r < heapSize && list[r][1] > list[largest][1]) {
largest = r
}
if (largest !== i) {
swap(list, i, largest)
maxHeapify(list, largest, heapSize)
}
}
//交换
function swap(arr, i, j) {
;[arr[i], arr[j]] = [arr[j], arr[i]]
}
}
const nums = [1, 10, 3, 8, 10, 9, 1, 4],
k = 2
console.log('🌰', topKFrequentHeap(nums, k)){}
init maxHeap ["1,2","10,2","3,1","8,1","9,1","4,1"]
5 ["10,2","4,1","3,1","8,1","9,1","1,2"]
4 ["9,1","4,1","3,1","8,1","10,2","1,2"]
🌰 [10,1]方法：快排的优化版
- 时间复杂度：O(n)
- 空间复杂度：O(n)
js
function topKFrequentQuickSort(nums, k) {
const map = new Map()
const len = nums.length
for (let i = 0; i < len; i++) {
const val = nums[i]
map.set(val, (map.get(val) || 0) + 1)
}
const list = [...map.entries()]
return quickSort(0, list.length - 1).map(a => a[0])
function quickSort(left, right) {
console.log(list.map(i => i.toString()))
if (list.length <= 1) return list
let pivotIndex = left //选择的中值
let pivotNum = list[pivotIndex][1]
console.log(
'left',
left,
'right',
right,
'k',
k,
'pivotIndex',
pivotIndex,
'pivot',
list[pivotIndex],
)
if (left < right) {
//与中值比较，大的往前放，小的往后放
for (let i = left + 1; i <= right; i++) {
if (list[i][1] >= pivotNum) {
// 碰到大于等于的值，先前进一步
pivotIndex++
/**
* i > pivotIndex 就是往后push的意思
* i === pivotIndex ，当前和前一个交换
* */
if (i > pivotIndex) {
;[list[pivotIndex], list[i]] = [list[i], list[pivotIndex]]
} else {
;[list[pivotIndex - 1], list[i]] = [list[i], list[pivotIndex - 1]]
}
}
}
console.log(
'after sort, pivotIndex',
pivotIndex,
list.map(a => a.toString()),
)
console.log('------')
}
if (pivotIndex === k - 1) {
return list.slice(0, k)
} else if (pivotIndex > k) {
return quickSort(left, pivotIndex)
} else {
return quickSort(pivotIndex + 1, right)
}
}
}
const nums = [1, 10, 7, 3, 8, 1, 7, 1, 3],
k = 3
// const nums = [1, 1, 1, 2, 2, 3],
// k = 2
const res = topKFrequentQuickSort(nums, k)
console.log('🌰', res)["1,3","10,1","7,2","3,2","8,1"]
left 0 right 4 k 3 pivotIndex 0 pivot [1,3]
after sort, pivotIndex 0 ["1,3","10,1","7,2","3,2","8,1"]
------
["1,3","10,1","7,2","3,2","8,1"]
left 1 right 4 k 3 pivotIndex 1 pivot [10,1]
after sort, pivotIndex 4 ["1,3","7,2","3,2","8,1","10,1"]
------
["1,3","7,2","3,2","8,1","10,1"]
left 1 right 4 k 3 pivotIndex 1 pivot [7,2]
after sort, pivotIndex 2 ["1,3","3,2","7,2","8,1","10,1"]
------
🌰 [1,3,7]