字节青训-查找热点数据问题

问题描述

给你一个整数数组 nums 和一个整数 k，请你返回其中出现频率前 k 高的元素。请按升序排列。

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

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

测试样例

样例1：

输入：nums = [1, 1, 1, 2, 2, 3], k = 2
输出：[1,2]

样例2：

输入：nums = [1], k = 1
输出：[1]

样例3：

输入：nums = [4, 4, 4, 2, 2, 2, 3, 3, 1], k = 2
输出：[2,4]

解题思路： 

用一个去重的数组对每一个出现的数字计数然后按顺序得出前n个数字就行

数据结构：

具体来说，用unordered_map 记录每个数字的频率。

然后将map中的数据添加到 vector 向量中。

接着是排序: 使用 sort 函数对 result 向量进行排序，排序依据是元素的频率（降序）。

输出格式的转换：

构建返回字符串: 遍历排序后的 result 向量的前 k 个元素，将它们转换为字符串并使用逗号分隔，

存储在 stringstream 中。

返回结果: 将 stringstream 中的内容转换为字符串并返回。

算法步骤

1. 频率计数：使用 Counter 统计每个元素的出现频率。
2. 选择前 k 个高频元素：
   • 一种方法是使用最小堆（min-heap）来维护当前的前 k 个高频元素。这样可以在 O(n log k) 的时间复杂度内完成。
   • 另一种方法是使用快速选择算法（Quickselect）来找到第 k 个高频元素，然后提取前 k 个高频元素。这种方法的平均时间复杂度是 O(n)。
3. 排序：最后，对前 k 个高频元素按元素值进行升序排序。

C++代码如下：

#include <iostream>  
#include <vector>  
#include <unordered_map>  
#include <queue>  
#include <sstream>  
#include <algorithm>  using namespace std;  string topKFrequent(vector<int>& nums, int k) {  // 使用哈希表记录每个元素的频率  unordered_map<int, int> freqMap;  for (int num : nums) {  freqMap[num]++;  }  vector<pair<int,int>> result;for(auto x : freqMap){result.push_back(x);}sort(result.begin(), result.end(), [](const pair<int, int>& a, const pair<int, int>& b) {return a.second > b.second;});stringstream ss;for (size_t i = 0; i < k; ++i) {  ss << result[i].first;  if (i < k - 1) {  ss << ",";  }  }return ss.str();
}   int main() {//  You can add more test cases herestd::vector<int> nums1 = {1, 1, 1, 2, 2, 3};std::vector<int> nums2 = {1};//cout << topKFrequent(nums1, 2) << endl;std::cout << (topKFrequent(nums1, 2) == "1,2") << std::endl;std::cout << (topKFrequent(nums2, 1) == "1") << std::endl;return 0;
}

Python代码如下：

from collections import Counterdef solution(nums, k):# 使用Counter记录每个元素的频率freq_map = Counter(nums)# 将频率map转化为列表，并先按频率降序，再按元素值升序排序result = sorted(freq_map.items(), key=lambda x: (-x[1], x[0]))# 获取频率最高的前k个元素top_k = [result[i][0] for i in range(k)]return top_kif __name__ == "__main__":# 测试用例nums1 = [1, 1, 1, 2, 2, 3]nums2 = [1]nums3 = [4, 4, 4, 2, 2, 2, 3, 3, 1]# 输出测试结果print(solution(nums1, 2) == [1, 2])  # 输出: Trueprint(solution(nums2, 1) == [1])  # 输出: Trueprint(solution(nums3, 2) == [2, 4])  # 输出: True

 通过咯，感觉这个困难题的难度一般，主要是输出的格式需要自己去转换

这么一看python这么短，真是派派又森森呀~