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 <= 105
  • k 的取值范围是 [1, 数组中不相同的元素的个数]
  • 题目数据保证答案唯一,换句话说,数组中前 k 个高频元素的集合是唯一的

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

代码参考:

package main

import (
    "fmt"
    "sort"
)

func main() {
    fmt.Println(topKFrequent([]int{2, 2, 1, 1, 1, 3}, 2)) // [1, 2]
}

// 和 451 很像
// 自己重新定义优先队列的优先度排序即可
type Priority struct {
    n int // num
    p int // priority
}

func topKFrequent(nums []int, k int) []int {
    n2p := make(map[int]int)
    for _, n := range nums {
        n2p[n]++
    }

    var priorities []Priority
    for n, p := range n2p {
        priorities = append(priorities, Priority{n, p})
    }

    sort.Slice(priorities, func(i, j int) bool {
        return priorities[i].p > priorities[j].p
    })

    res := make([]int, k) // 应对 k 做合法校验
    for i, p := range priorities[:k] {
        res[i] = p.n
    }
    return res
}
最后编辑: kuteng  文档更新时间: 2021-06-05 10:16   作者:kuteng