leecode 解题总结:347. Top K Frequent Elements

    xiaoxiao2021-03-26  3

    #include <iostream> #include <stdio.h> #include <vector> #include <string> #include <unordered_map> using namespace std; /* 问题: Given a non-empty array of integers, return the k most frequent elements. For example, Given [1,1,1,2,2,3] and k = 2, return [1,2]. Note: You may assume k is always valid, 1 ≤ k ≤ number of unique elements. Your algorithm's time complexity must be better than O(n log n), where n is the array's size. 分析:此题要求计算数组中前k个出现次数的元素。时间复杂度要好于O(n log n)。 如果用统计排序,那么由于没有告诉数组中元素值的范围,并不好计算,会溢出。 至少需要记录每个元素出现的次数,然后选择前K个。 用map。map本质上是红黑树,插入的时间复杂度为O(logN),查找 的时间复杂度为O(logN)。遍历数组,插入map,时间复杂度为O(N*logN)。 遍历map,寻找前k个出现次数最多的,时间复杂度O(N*logN) 此题和寻找前k个最大的数不同,寻找前k个最大的数用优先级队列(本质是堆) 输入: 6(数组元素个数) 2(k) 1 1 1 2 2 3 输出: 1 2 报错: Input: [1,2] 2 Output: [1] Expected: [1,2] 关键 1 参考:https://leetcode.com/problems/top-k-frequent-elements/?tab=Solutions 采用哈希建立<数字,出现次数>的映射,然后出现次数最多不会超过n,建立一个数组 数组中A[i]表示出现次数为i的元素为A[i],将该数组逆序输出k个即可。 哈希统计,O(n),存入数组O(n)。厉害,建立了两次映射。 实际是对次数建立桶排序 */ class Solution { public: vector<int> topKFrequent(vector<int>& nums, int k) { vector<int> result; if(nums.empty() || k <= 0) { return result; } unordered_map<int , int> numToTimes; int size = nums.size(); //统计数字到出现次数的映射 for(int i = 0 ; i < size ; i++) { if(numToTimes.find(nums.at(i)) != numToTimes.end()) { numToTimes[nums.at(i)]++; } else { numToTimes[nums.at(i)] = 1; } } //建立<出现次数,[数字]>的映射,从后向前遍历k个即为所求,但是出现次数可能是相同的,数字必须用数组表示 vector< vector<int> > timesToNum(size + 1 , vector<int>()); for(unordered_map<int , int>::iterator it = numToTimes.begin(); it != numToTimes.end() ; it++) { timesToNum.at(it->second).push_back(it->first); } int count = 0; for(int i = size ; i >= 0 ; i--) { if(!timesToNum.at(i).empty() ) { int len = timesToNum.at(i).size(); for(int j = 0 ; j < len ; j++) { if(count < k) { result.push_back( timesToNum.at(i).at(j) ); count++; } if(count >= k) { return result; } } } } return result; } }; void print(vector<int>& result) { if(result.empty()) { cout << "no result" << endl; return; } int size = result.size(); for(int i = 0 ; i < size ; i++) { cout << result.at(i) << " " ; } cout << endl; } void process() { vector<int> nums; int value; int num; Solution solution; vector<int> result; int k; while(cin >> num >> k ) { nums.clear(); for(int i = 0 ; i < num ; i++) { cin >> value; nums.push_back(value); } result = solution.topKFrequent(nums , k); print(result); } } int main(int argc , char* argv[]) { process(); getchar(); return 0; }
    转载请注明原文地址: https://ju.6miu.com/read-500296.html

    最新回复(0)