347.前K个高频元素

Aug 30, 2024

         https://leetcode.cn/problems/top-k-frequent-elements/

                         347. 前 K 个高频元素
                    中等  │ 1880  │ 64.0% 的 933K

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

󰛨 示例 1：

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

󰛨 示例 2：

│ 输入： nums = [1], k = 1
│ 输出： [1]

 提示：

* 1 <= nums.length <= 10^5

* k 的取值范围是 [1, 数组中不相同的元素的个数]

* 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

进阶：你所设计算法的时间复杂度必须优于 O(n log n) ，其中 n 是数组大小。

解法

func topKFrequent(nums []int, k int) []int {
    m := map[int]int{}
    for _, v := range nums {
        m[v]++
    }

    r := make([][]int, len(nums)+1)
    for k, v := range m {
        r[v] = append(r[v], k)
    }

    ans := []int{}
    for i:=len(r)-1; i>=0; i-- {
        v := r[i]
        if len(v) == 0 {
            continue
        }
        if len(ans) >= k {
            break
        }
        ans = append(ans, v...)
    }
    return ans
}