LeetCode347前k个高频元素js-创新互联
力扣题目链接
题目:
给定一个非空的整数数组，返回其中出现频率前 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 是数组的大小。
- 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
- 你可以按任意顺序返回答案。
因为js没有小顶堆(用数组构造的一棵递增的二叉树,数组头部就是最小值),所以需要自己构造:
构建小顶堆涉及的节点关系公式:
假设节点索引为n(n>=0):
父节点: n-1/2
左子节点: 2n+1
右子节点: 2n+2
class Heap {
constructor(compareFn) {
this.compareFn = compareFn
this.queue = []
}
// 添加
push(item) {
// 推入元素
this.queue.push(item)
// 上浮
let index = this.size() - 1 // 记录推入元素下标
let parent = Math.floor((index - 1) / 2) // 记录父节点下标
// 注意compare参数顺序
while (parent >= 0 && this.compare(parent, index) >0) {
;[this.queue[index], this.queue[parent]] = [
this.queue[parent],
this.queue[index],
]
// 更新下标
index = parent
parent = Math.floor((index - 1) / 2)
}
}
// 获取堆顶元素并移除
pop() {
// 堆顶元素
const out = this.queue[0]
// 移除堆顶元素 填入最后一个元素
this.queue[0] = this.queue.pop()
// 下沉
let index = 0 // 记录下沉元素下标
let left = 1 // left 是左子节点下标 left + 1 则是右子节点下标
let searchChild = this.compare(left, left + 1) >0 ? left + 1 : left // 从左右子叶找出一个较小的值进行比较
// 如果下沉节点要大于子节点 则交换位置
while (
searchChild !== undefined &&
this.compare(index, searchChild) >0
) {
// 注意compare参数顺序
;[this.queue[index], this.queue[searchChild]] = [
this.queue[searchChild],
this.queue[index],
]
// 更新下标
index = searchChild
left = 2 * index + 1
searchChild = this.compare(left, left + 1) >0 ? left + 1 : left // 重新比较出左右子叶较小的一个供下一轮循环进行比较
}
return out
}
size() {
return this.queue.length
}
// 使用传入的 compareFn 比较两个位置的元素
compare(index1, index2) {
// 处理下标越界问题
if (this.queue[index1] === undefined) return 1
if (this.queue[index2] === undefined) return -1
return this.compareFn(this.queue[index1], this.queue[index2])
}
}有小顶堆后就可以用在题目里了:
const topKFrequent = function (nums, k) {
const map = new Map() // 创建哈希表
// 以key为num value为num出现的次数存入哈希表
for (const num of nums) {
map.set(num, (map.get(num) || 0) + 1)
}
// 创建小顶堆
const heap = new Heap((a, b) =>a[1] - b[1]) // a-b从小到大 类似sort函数
// entry 是一个长度为2的数组，0位置存储key，1位置存储value [[num, frequent]]
for (const entry of map.entries()) {
heap.push(entry)
// 当堆大小满足k时 则开始pop 堆里只保留topk
if (heap.size() >k) {
heap.pop()
}
}
const result = []
// 小顶堆pop出来的就是最小值 一个个pop出来 res数组从后往前放 这样就是从大到小的顺序了
for (let i = heap.size() - 1; i >= 0; i--) {
result[i] = heap.pop()[0]
}
return result
}
console.log(topKFrequent([1, 2, 2, 2, 3, 3, 3, 3, 4, 5, 6, 6, -1], 3)) // [3,2,6]不用小顶堆的做法,直接怼map.entries()进行排序:
function topKFrequent2(nums, k) {
const map = new Map() // 创建哈希表
// 以key为num value为num出现的次数存入哈希表
for (const num of nums) {
map.set(num, (map.get(num) || 0) + 1)
}
const result = [...map.entries()]
.sort((a, b) =>b[1] - a[1]) // 按照value排序
.slice(0, k) // 获取前k个元素
.map((e) =>e[0]) // 返回num的集合
return result
}
console.log(topKFrequent2([1, 2, 2, 2, 3, 3, 3, 3, 4, 5, 6, 6, -1], 3)) // [3,2,6]代码随想录链接
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
标题名称：LeetCode347前k个高频元素js-创新互联
文章URL：http://cdiso.cn/article/pgsdi.html
