问题描述
给你一个整数数组 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 中的内容转换为字符串并返回。
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代码如下：
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这么短，真是派派又森森呀~
