LeetCode 347. 前 K 个高频元素

题目链接：LeetCode 347. 前 K 个高频元素

题意：

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

解题思路：

(哈希表，计数排序) O(n)

1. 首先用哈希表统计出所有数出现的次数。
2. 由于所有数出现的次数都在 1 到 n 之间，所以我们可以用计数排序的思想，统计出次数最多的前 k 个元素的下界。
3. 然后将所有出现次数大于等于下界的数输出。

时间复杂度分析：用哈希表统计每个数出现次数的计算量是 O(n)，计数排序的计算量是 O(n)，最终用下界过滤结果的计算量也是 O(n)，所以总时间复杂度是 O(n)。

完整代码如下：

func topKFrequent(nums []int, k int) []int {
    // 首先用哈希表统计出所有数出现的次数。
    // 由于所有数出现的次数都在 1 到 n之间，所以我们可以用计数排序的思想，统计出次数最多的前 k 个元素的下界。
    // 然后将所有出现次数大于等于下界的数输出。
    // 时间复杂度分析：用哈希表统计每个数出现次数的计算量是 O(n)，计数排序的计算量是 O(n)，最终用下界过滤结果的计算量也是 O(n)，所以总时间复杂度是 O(n)

    count:=map[int]int{}//统计每个元素出现多少次
    
    for _ ,v :=range nums{  //用哈希表统计每个数出现次数的计算量是 O(n)
        count[v]++    
    }
    n:=len(nums)+1
    s:=make([]int,n) //表示出现每种次数的元素的个数是多少
    for _,v:=range count{   //计数排序
        s[v]++
    }
    i:=len(nums)
    t:=0
    for t < k{     //得到前k个的分界线
        t += s[i]
        i--
    }
    var res []int
    for k,v:=range count{  // 最终用下界过滤结果
        if v > i{
            res = append(res,k)
        }
    }
    return res

}