347-前K个高频元素.md

347. 前 K 个高频元素

leecode原题

题目

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

提示：

• 1 <= nums.length <= 105
• k 的取值范围是 [1, 数组中不相同的元素的个数]
• 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

解题思路

思路

实现

源码

// 使用快排实现
func topKFrequent(nums []int, k int) []int {
	res := []int{}

	// 使用map统计词频
	countMap := make(map[int]int)
	for _, num := range nums {
		countMap[num]++
	}

	for key, _ := range countMap {
		res = append(res, key)
	}
	//核心思想：排序
	//可以不用包函数，自己实现快排
	sort.Slice(res, func(a, b int) bool {
		return countMap[res[a]] > countMap[res[b]]
	})
	return res[:k]
}