2015年全球网站优秀设计师,微网站开发的比较总结,广西贺州建设局网站,昆山网站建设方案优化公司问题描述 给你一个整数数组 nums 和一个整数 k#xff0c;请你返回其中出现频率前 k 高的元素。请按升序排列。 1 nums.length 10^5k 的取值范围是 [1, 数组中不相同的元素的个数]题目数据保证答案唯一#xff0c;换句话说#xff0c;数组中前 k 个高频元素的集合… 问题描述 给你一个整数数组 nums 和一个整数 k请你返回其中出现频率前 k 高的元素。请按升序排列。 1 nums.length 10^5k 的取值范围是 [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 中的内容转换为字符串并返回。 算法步骤
频率计数使用 Counter 统计每个元素的出现频率。选择前 k 个高频元素 一种方法是使用最小堆min-heap来维护当前的前 k 个高频元素。这样可以在 O(n log k) 的时间复杂度内完成。另一种方法是使用快速选择算法Quickselect来找到第 k 个高频元素然后提取前 k 个高频元素。这种方法的平均时间复杂度是 O(n)。排序最后对前 k 个高频元素按元素值进行升序排序。
C代码如下
#include iostream
#include vector
#include unordered_map
#include queue
#include sstream
#include algorithm using namespace std; string topKFrequent(vectorint nums, int k) { // 使用哈希表记录每个元素的频率 unordered_mapint, int freqMap; for (int num : nums) { freqMap[num]; } vectorpairint,int result;for(auto x : freqMap){result.push_back(x);}sort(result.begin(), result.end(), [](const pairint, int a, const pairint, 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::vectorint nums1 {1, 1, 1, 2, 2, 3};std::vectorint 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(), keylambda 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这么短真是派派又森森呀~
