C++ 解法, 执行用时: 11ms, 内存消耗: 2612KB, 提交时间: 2021-09-09
class Solution {
public:
/**
* return topK string
* @param strings string字符串vector strings
* @param k int整型 the k
* @return string字符串vector<vector<>>
*/
struct cmp{
bool operator() (const pair<string, int> &p1, const pair<string, int> &p2)
{
return p1.second > p2.second || (p1.second == p2.second && p1.first < p2.first);
}
};
vector<vector<string> > topKstrings(vector<string>& strings, int k) {
// write code here
vector<vector<string> > res;
if(strings.size() == 0)
return res;
unordered_map<string, int> hash;
for(auto c : strings)
hash[c] ++;
priority_queue<pair<string, int>, vector<pair<string, int>>, cmp> q;
int i = 0;
for(auto c : hash)
{
if(i < k) q.push(c);
else
{
if(c.second > q.top().second || (c.second == q.top().second && c.first < q.top().first))
{
q.pop();
q.push(c);
}
}
i++;
}
while(!q.empty())
{
res.push_back({q.top().first, to_string(q.top().second)});
q.pop();
}
reverse(res.begin(), res.end());
return res;
}
};
C++ 解法, 执行用时: 11ms, 内存消耗: 2616KB, 提交时间: 2021-09-17
class Solution {
public:
/**
* return topK string
* @param strings string字符串vector strings
* @param k int整型 the k
* @return string字符串vector<vector<>>
*/
struct cmp {
bool operator()(pair<string, int>& a, pair<string, int>& b) {//频率小顶堆，频率相同的话按字符串大顶堆
// return a.second > b.second || (a.second == b.second && a.first < b.first);
if(a.second == b.second) {
return a.first < b.first;
}
return a.second > b.second;
}
};
vector<vector<string> > topKstrings(vector<string>& strings, int k) {
// write code here
vector<vector<string>> ans;
unordered_map<string, int> map;
for(auto & s : strings) map[s]++;
priority_queue<pair<string, int>, vector<pair<string, int> >, cmp> q;
for(auto ite = map.begin(); ite != map.end(); ite++) {
if(q.size() < k) {
q.push(pair<string, int>(ite->first, ite->second));
} else if(ite->second > q.top().second || (ite->second == q.top().second && ite->first < q.top().first)) {
q.pop();
q.push(pair<string, int>{ite->first, ite->second});
}
}
while(!q.empty()) {
ans.push_back(vector<string> {q.top().first, to_string(q.top().second)});
q.pop();
}
reverse(ans.begin(), ans.end());
return ans;
}
};
C++ 解法, 执行用时: 11ms, 内存消耗: 2624KB, 提交时间: 2021-09-13
struct com{
bool operator()(const pair<string,int>&l,const pair<string,int>&r)const{
return l.second>r.second||((l.second==r.second)&&l.first<r.first);
}
};
class Solution {
public:
/**
* return topK string
* @param strings string字符串vector strings
* @param k int整型 the k
* @return string字符串vector<vector<>>
*/
vector<vector<string> > topKstrings(vector<string>& strings, int k) {
// write code here
vector<vector<string>>res;
if(strings.size()==0) return res;
unordered_map<string,int>hashmap;
for(auto c:strings){
hashmap[c]++;
}
priority_queue<pair<string,int>,vector<pair<string,int>>,com>q;
for(auto it=hashmap.begin();it!=hashmap.end();it++){
if(q.size()<k){
q.push(*it);
}else{
if(it->second>q.top().second||(it->second==q.top().second&&it->first<q.top().first)){
q.pop();
q.push(*it);
}
}
}
while(!q.empty()){
pair<string,int>p=q.top();
q.pop();
vector<string>v;
v.push_back(p.first);
v.push_back(to_string(p.second));
res.push_back(v);
v.clear();
}
reverse(res.begin(), res.end());
return res;
}
};
C++ 解法, 执行用时: 11ms, 内存消耗: 2632KB, 提交时间: 2021-09-09
class Solution {
public:
/**
* return topK string
* @param strings string字符串vector strings
* @param k int整型 the k
* @return string字符串vector<vector<>>
*/
struct cmp{
bool operator()(pair<string,int>&p1,pair<string,int>&p2)
{
return p1.second>p2.second||(p1.second==p2.second&&p1.first<p2.first);
}
};
vector<vector<string> > topKstrings(vector<string>& strings, int k) {
// write code here
vector<vector<string>> res;
if(strings.size()==0) return res;
unordered_map<string, int> m;
for(string& str:strings)
{
++m[str];
}
priority_queue<pair<string,int>,vector<pair<string,int>>,cmp> q;
int i=0;
for(auto c:m)
{
if(i<k) q.push(c);
else{
if(c.second>q.top().second||(c.second==q.top().second&&c.first<q.top().first))
{
q.pop();
q.push(c);
}
}
++i;
}
while(!q.empty())
{
vector<string> v({q.top().first,to_string(q.top().second)});
res.push_back(v);
q.pop();
}
reverse(res.begin(), res.end());
return res;
}
};
C++ 解法, 执行用时: 11ms, 内存消耗: 2736KB, 提交时间: 2021-09-14
class Solution {
public:
/**
* return topK string
* @param strings string字符串vector strings
* @param k int整型 the k
* @return string字符串vector<vector<>>
*/
struct cmp
{
bool operator()(const pair<string, int>&m1,const pair<string, int>&m2)
{
return m1.second>m2.second||(m1.second==m2.second&&m1.first<m2.first);
}
};
vector<vector<string> > topKstrings(vector<string>& strings, int k) {
// write code here
vector<vector<string>>res;
if(strings.size()==0)
return {};
unordered_map<string,int>m;
for(auto it:strings)
{
m[it]++;
}
priority_queue<pair<string,int>,vector<pair<string, int>>,cmp>pri;
int i=0;
for(auto it:m)
{
if(i<k)
{
pri.push(pair<string,int>{it.first,it.second});
}
else if(it.second>pri.top().second||(it.second==pri.top().second&&it.first<pri.top().first))
{
pri.pop();
pri.push(pair<string,int>{it.first,it.second});
}
i++;
}
while(!pri.empty())
{
res.push_back(vector<string>{pri.top().first,to_string(pri.top().second)});
pri.pop();
}
reverse(res.begin(), res.end());
return res;
}
};
，每个字符串长度 
，
)
，时间复杂度)