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

核心思想

O（nlgn）的思路很好想，sort，再统计出现次数，按出现次数从高到低排序，输出。

优化：O(n)

堆或者桶排序，堆要声明一堆heap相关函数，用着麻烦，这里用桶排序。

桶排序（Bucket Sort）是一种分布式排序算法，它的基本思想是将待排序的数据分到不同的 “桶” 中，然后对每个桶内的数据进行排序，最后按照顺序依次取出每个桶中的数据，从而得到一个有序的序列。

桶排序算法步骤

1. 划分桶：
   • 根据待排序数据的范围和数据量，确定桶的数量和每个桶的取值范围。例如，如果待排序数据范围是 0 到 100，且分为 10 个桶，那么每个桶的取值范围就是 0 - 9、10 - 19、20 - 29，以此类推。
2. 分配数据到桶：
   • 遍历待排序的数据，根据数据的值将其分配到对应的桶中。例如，值为 25 的数据会被分配到取值范围为 20 - 29 的桶中。
3. 桶内排序：
   • 对每个桶内的数据进行排序。可以使用任何其他排序算法，如插入排序、快速排序等。由于每个桶内的数据量相对较小，所以排序效率通常较高。
4. 合并桶：
   • 按照桶的顺序，依次将每个桶内排好序的数据取出，最终得到一个完整的有序序列。

代码

sort大法：

import "sort"
func topKFrequent(nums []int, k int) []int {
    n := len(nums)
    if n == 1{
        return nums
    }
    // 排序
    sort.Ints(nums)
    type pair struct {
        num int
        cnt int
    }
    pairs := make([]pair, n+1)
    pre, i := math.MaxInt, 0
    // 统计频数
    for _, x := range nums {
        if x == pre {
            pairs[i].cnt++
        }else{
            i++
            pairs[i].num, pairs[i].cnt = x, 1
            
        }
        pre = x
    }
    // 将pairs按cnt排序
    sort.Slice(pairs, func(i, j int)bool {
        return pairs[i].cnt >pairs[j].cnt
    })
    ans := []int{}
    for j := 0; j < k; j++ {
        ans = append(ans, pairs[j].num)
    }
    return ans

}

桶排序：

func topKFrequent(nums []int, k int) []int {
     // 统计元素频数
    m := make(map[int]int)
    maxCnt := 0 // 记下最大的频数，方便开辟桶
    for _, num := range nums {
        m[num]++
        maxCnt = max(maxCnt, m[num])
    }

    // 把频数相同的放入到一个桶中
    buckets := make([][]int, maxCnt+1)
    for num, cnt := range m {
        buckets[cnt] = append(buckets[cnt], num)
    }

    // 倒序遍历桶
    ans := make([]int, 0, k) // 预分配空间
    for i := maxCnt; i >= 0 && len(ans) < k; i-- {
        ans = append(ans, buckets[i]...)
    }
    return ans
}