#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
