题目

给定一个整数数组 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 是数组大小。

注意：本题与主站 347 题相同

解题思路分析

1、哈希辅助；时间复杂度O(nlog(n))，空间复杂度O(n)

func topKFrequent(nums []int, k int) []int {
   m := make(map[int]int)
   for i := 0; i < len(nums); i++ {
      m[nums[i]]++
   }
   arr := make([][2]int, 0)
   for k, v := range m {
      arr = append(arr, [2]int{k, v})
   }
   sort.Slice(arr, func(i, j int) bool {
      return arr[i][1] > arr[j][1]
   })
   res := make([]int, 0)
   for i := 0; i < k; i++ {
      res = append(res, arr[i][0])
   }
   return res
}

2、堆；时间复杂度O(nlog(n))，空间复杂度O(n)

func topKFrequent(nums []int, k int) []int {
   m := make(map[int]int)
   for i := 0; i < len(nums); i++ {
      m[nums[i]]++
   }
   var h IntHeap
   heap.Init(&h)
   for k, v := range m {
      heap.Push(&h, [2]int{k, v})
   }
   res := make([]int, 0)
   for h.Len() > 0 && k > 0 {
      k--
      node := heap.Pop(&h).([2]int)
      res = append(res, node[0])
   }
   return res
}

type IntHeap [][2]int

func (h IntHeap) Len() int            { return len(h) }
func (h IntHeap) Less(i, j int) bool  { return h[i][1] > h[j][1] }
func (h IntHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) { *h = append(*h, x.([2]int)) }
func (h *IntHeap) Pop() interface{} {
   old := *h
   n := len(old)
   x := old[n-1]
   *h = old[0 : n-1]
   return x
}

3、桶排序；时间复杂度O(n)，空间复杂度O(n)

func topKFrequent(nums []int, k int) []int {
   m := make(map[int]int)
   for i := 0; i < len(nums); i++ {
      m[nums[i]]++
   }
   arr := make([][]int, len(nums)+1)
   temp := make(map[int][]int)
   for key, value := range m {
      temp[value] = append(temp[value], key)
      arr[value] = append(arr[value], key)
   }
   res := make([]int, 0)
   for i := len(arr) - 1; i >= 0; i-- {
      // 避免出现0=>x次的情况
      if _, ok := temp[i]; ok {
         for j := 0; j < len(arr[i]); j++ {
            k--
            if k < 0 {
               break
            }
            res = append(res, arr[i][j])
         }
      }
   }
   return res
}

总结

Medium题目，题目同leetcode 347.前K个高频元素