[MarsCode 系列] 查找热点数据

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

• $1<=nums.length<=10^5$
• k 的取值范围是 [1, 数组中不相同的元素的个数]
• 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

你所设计算法的时间复杂度必须优于 $O(nlogn)$ ，其中 n 是数组大小。

示例 1

输入: nums = [1,1,1,2,2,3], k = 2

输出: [1,2]

示例 2

输入: nums = [1], k = 1

输出: [1]

解题

这道题目，如果直接关键字排序的话可能会超时，在这里我使用了堆来优化时间复杂度，使其可以满足题目的需求。

c++：

#include <iostream>
#include <unordered_map>
#include <queue>// 定义一个比较函数，用于优先队列的排序
struct Compare {bool operator()(const std::pair<int, int>& a, const std::pair<int, int>& b) {return a.second < b.second;}
};// 优化后的 solution 函数
std::vector<int> Solution(const std::vector<int>& nums, int k) {std::unordered_map<int, int> frequencyMap;std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, Compare> pq;// 统计频率并维护优先队列for (int num : nums) {frequencyMap[num]++;pq.push({num, frequencyMap[num]});}std::vector<int> result;while (k --) {result.push_back(pq.top().first);pq.pop();}return result;
}bool EqualArr(std::vector<int> a, std::vector<int> b) {bool flag = true;for (int i = 0; i < a.size(); i ++) {if (a[i] != b[i]) {flag = false;}}return flag;
}int main() {std::cout << EqualArr(Solution({1, 1, 1, 2, 2, 3}, 2), std::vector<int>(1, 2)) << std::endl;  // 输出 1 表示通过std::cout << EqualArr(Solution({1}, 1), std::vector<int>(1)) << std::endl;                    // 输出 1 表示通过return 0;
}

go:

package mainimport ("container/heap""fmt"
)type Element struct {num   intcount int
}// 定义一个最小堆
type MinHeap []Elementfunc (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].count < h[j].count }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }func (h *MinHeap) Push(x interface{}) {*h = append(*h, x.(Element))
}func (h *MinHeap) Pop() interface{} {old := *hn := len(old)x := old[n-1]*h = old[0 : n-1]return x
}func topKFrequent(nums []int, k int) []int {frequencyMap := make(map[int]int)for _, num := range nums {frequencyMap[num]++}minHeap := &MinHeap{}heap.Init(minHeap)for num, count := range frequencyMap {heap.Push(minHeap, Element{num, count})if minHeap.Len() > k {heap.Pop(minHeap)}}result := make([]int, k)for i := k - 1; i >= 0; i-- {element := heap.Pop(minHeap).(Element)result[i] = element.num}return result
}func EqualArr(a []int, b []int) bool {flag := truefor i := 0; i < len(a); i ++ {if a[i] != b[i] {flag = false}}return flag
}func main() {fmt.Println(EqualArr(topKFrequent([]int{1, 1, 1, 2, 2, 3}, 2), []int{1, 2}))fmt.Println(EqualArr(topKFrequent([]int{1}, 1), []int{1}))
}