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]
}