【Day46】347.前K个高频元素

文章目录347.前K个高频元素题目思路代码实现Go347.前K个高频元素题目给你一个整数数组 nums 和一个整数 k 请你返回其中出现频率前 k 高的元素。你可以按任意顺序返回答案。示例 1输入nums [1,1,1,2,2,3], k 2输出[1,2]示例 2输入nums [1], k 1输出[1]示例 3输入nums [1,2,1,2,1,2,3,1,3,2], k 2输出[1,2]提示1 nums.length 10^5-10^4 nums[i] 10^4k 的取值范围是 [1, 数组中不相同的元素的个数]题目数据保证答案唯一换句话说数组中前 k 个高频元素的集合是唯一的思路先统计每个数字出现的次数再反复找出现最多的数字找够 K 个就是答案。遍历数组使用map统计每个数字的出现频率key 存储数字value 存储该数字出现的次数。循环遍历 map每次找到当前频率最高的那个数字。把找到的数字加入结果切片并将它的频率设为 0确保下次不会再被选中。重复步骤 2、3直到把所有数字按频率从高到低取完。最后截取结果切片的前 K 个元素返回就是出现频率最高的前 K 个元素。代码实现Gopackagemainimportfmt// 功能给定数组 nums返回出现频率最高的前 k 个元素// 解法暴力查找法 —— 统计频率 → 每次取最大 → 取前k个functopKFrequent(nums[]int,kint)[]int{// 边界情况如果数组长度比k还小直接返回nil题目一般不会出现iflen(nums)k{returnnil}// 1. 用 map 统计每个数字出现的次数频率// key数组中的数字// value该数字出现的次数freqMap:make(map[int]int)fori:0;ilen(nums);i{freqMap[nums[i]]}// 存放结果的切片res:[]int{}// 2. 循环遍历map每次找到当前频率最大的数字加入结果// 这里循环len(freqMap)次把所有数字按频率从高到低取出来fori:0;ilen(freqMap);i{maxCount:0// 当前最大的频率maxNum:0// 当前频率最大的数字// 遍历map找到当前频率最大的数字// key 存储数字value 存储该数字出现的次数fornum,count:rangefreqMap{ifcountmaxCount{maxCountcount// 更新最大频率maxNumnum// 更新对应的数字}}// 把频率最大的数字加入结果切片resappend(res,maxNum)// 把这个数字的频率设为0下次遍历就不会再选到它了标记已使用freqMap[maxNum]0}// 3. 取前k个就是答案频率最高的前k个元素// 左闭右开returnres[:k]}funcmain(){nums:[]int{1,1,1,2,2,3}k:2fmt.Println(topKFrequent(nums,k))// 输出[1 2]nums2:[]int{5,1,1,2,2,0,0}k2:3fmt.Println(topKFrequent(nums2,k2))// 输出[1 2 0]}1. 时间复杂度O(n²)遍历数组统计频率O(n)每次遍历 map 找最大值一共找 n 次O(n) * O(n) O(n²)数据量大时效率低2. 空间复杂度O(n)使用了一个 map 存储所有数字的频率O(n)使用了结果切片O(k)→ 可忽略总空间O(n)