每日一题 --- 前 K 个高频元素[力扣][Go]

前 K 个高频元素

题目：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 是数组大小。

方法一：

排序，给定数字排序：

func topKFrequent(nums []int, k int) []int {
   m := make(map[int]int)
   for _, num := range nums {
      m[num]++
   }
   res := make([]int, 0)
   for key, _ := range m {
      res = append(res, key)
   }
   sort.Slice(res, func(i, j int) bool {
      return m[res[i]] > m[res[j]]
   })
   return res[:k]
}

方法二：

利用小根堆来做，思路：代码随想录 (programmercarl.com)

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

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

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

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

type IHeap [][2]int