哪里有手机网站制作公司,湛江网站制作推广,wordpress获取主页路径,iis服务器的默认网站前 K 个高频元素
题目#xff1a;347. 前 K 个高频元素
给你一个整数数组 nums 和一个整数 k #xff0c;请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1:
输入: nums [1,1,1,2,2,3], k 2
输出: [1,2]示例 2:
输入: nums [1], k 1
输出: …前 K 个高频元素
题目347. 前 K 个高频元素
给你一个整数数组 nums 和一个整数 k 请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1:
输入: nums [1,1,1,2,2,3], k 2
输出: [1,2]示例 2:
输入: nums [1], k 1
输出: [1]提示
1 nums.length 105k 的取值范围是 [1, 数组中不相同的元素的个数]题目数据保证答案唯一换句话说数组中前 k 个高频元素的集合是唯一的
**进阶**你所设计算法的时间复杂度 必须 优于 O(n log n) 其中 n 是数组大小。
方法一
排序给定数字排序
func topKFrequent(nums []int, k int) []int {m : make(map[int]int)for _, num : range nums {m[num]}res : make([]int, 0)for key, _ : range m {res append(res, key)}sort.Slice(res, func(i, j int) bool {return m[res[i]] m[res[j]]})return res[:k]
}方法二
利用小根堆来做思路代码随想录 (programmercarl.com)
func topKFrequent(nums []int, k int) []int {map_num : map[int]int{}//记录每个元素出现的次数for _, item : range nums {map_num[item]}h : IHeap{}heap.Init(h)//所有元素入堆堆的长度为kfor key, value : range map_num {heap.Push(h, [2]int{key, value})if h.Len() k {heap.Pop(h)}}res : make([]int, k)//按顺序返回堆中的元素for i : 0; i k; i {res[k-i-1] heap.Pop(h).([2]int)[0]}return res
}func (h IHeap) Swap(i, j int) {h[i], h[j] h[j], h[i]
}func (h *IHeap) Push(x interface{}) {*h append(*h, x.([2]int))
}func (h *IHeap) Pop() interface{} {old : *hn : len(old)x : old[n-1]*h old[0 : n-1]return x
}func (h IHeap) Len() int {return len(h)
}func (h IHeap) Less(i, j int) bool {return h[i][1] h[j][1]
}type IHeap [][2]int
