当前位置：首页 > article >正文

347. 前 K 个高频元素

article 2024/9/24 23:02:36

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 <= 10^5
k 的取值范围是 [1, 数组中不相同的元素的个数]

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

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

思路：

这道题目主要涉及到如下三块内容：

要统计元素出现频率
对频率排序
找出前k个高频元素

首先统计元素出现的频率，这一类的问题可以使用map来进行统计。

然后是对频率进行排序，可以直接使用库函数进行快速排序，不过时间复杂度是 $O (n l o g n)$ ，不太符合题目诉求，题目进阶要求是时间复杂度优于 $O (n l o g n)$ ，所以应该想到堆，实际上，求最大或者最小的k个数，大部分时候都是用堆解决的。

什么是堆呢？

堆是一棵完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子的值。如果父亲结点是大于等于左右孩子就是大顶堆，小于等于左右孩子就是小顶堆。

所以大家经常说的大顶堆（堆头是最大元素），小顶堆（堆头是最小元素），底层实现都是一样的，从小到大排就是小顶堆，从大到小排就是大顶堆。

思考一下，是使用小顶堆呢，还是大顶堆？

有的同学一想，题目要求前 k 个高频元素，那么果断用大顶堆啊。

那么问题来了，定义一个大小为k的大顶堆，在每次移动更新大顶堆的时候，每次弹出都把最大的元素弹出去了，那么怎么保留下来前k个高频元素呢。

所以如果使用大顶堆就要把所有元素都进行排序，那能不能只排序k个元素呢？

可以的，我们用小顶堆，因为要统计最大前k个元素，只有小顶堆每次将最小的元素弹出，最后小顶堆里积累的就是前k个最大元素。

Go 语言对于堆没有现成可使用的库，但是提供了heap包，只要实现 heap.Interface 接口要求的方法，然后，使用 heap.Init 初始化堆，就可以使用这个堆了。

heap包的Interface接口定义如下：

type Interface interface {
	sort.Interface
	Push(x any) // add x as element Len()
	Pop() any   // remove and return element Len() - 1.
}

sort包的Interface接口定义如下：

type Interface interface {
	Len() int
	Less(i, j int) bool
	Swap(i, j int)
}

所以我们要实现heap.Interface，需要实现五个方法。

注意：Len方法直接用h调用，但是Push和Pop方法则是用heap包的，然后将h作为了参数

Go代码如下：

func topKFrequent(nums []int, k int) []int {
    //使用小顶堆
    map_num:=map[int]int{}
    //记录每个元素出现的次数
    for _,item:=range nums{
        map_num[item]++
    }
    
    // 初始化堆
    h:=&IHeap{}
    heap.Init(h)
    //所有元素入堆，堆的长度为k
   // 注意：Len方法直接用h调用，但是Push和Pop方法则是用heap包的，然后将h作为了参数
    for 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
}

// 构建小顶堆
type IHeap [][2]int

func (h IHeap) Len()int {
    return len(h)
}

func (h IHeap) Less (i,j int) bool {
    return h[i][1]<h[j][1]
}

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{}{
    x:=(*h)[len(*h)-1]
    *h=(*h)[0:len(*h)-1]
    return x
}


// //方法二:利用O(nlogn)排序
// func topKFrequent(nums []int, k int) []int {
//     ans:=[]int{}
//     map_num:=map[int]int{}
//     for _,item:=range nums {
//         map_num[item]++
//     }
//     for key,_:=range map_num{
//         ans=append(ans,key)
//     }
//     //核心思想：排序
//     //可以不用包函数，自己实现快排
//     sort.Slice(ans,func (a,b int)bool{
//         return map_num[ans[a]]>map_num[ans[b]]
//     })
//     return ans[:k]
// }