背景:
我今天在一次在线实践面试中被问到了这个问题,我很难找出一个自定义的比较器进行排序。这是问题
问题:
实现一个文档扫描功能wordCountEngine,该功能接收一个字符串文档,并返回其中包含的所有唯一单词及其出现次数的列表,并按出现次数从高到低排序。如果两个或多个单词具有相同的计数,则应根据它们在原始句子中的顺序进行排序。假设所有字母都是英文字母。您的函数应不区分大小写,例如,“ Perfect”和“ perfect”一词应视为同一词。
引擎应去除标点符号(即使在单词中间),并使用空格分隔单词。
分析解决方案的时间和空间复杂性。尝试优化时间,同时保持多项式空间的复杂性。
示例:
输入:document =“实践完美。您只会 通过实践获得完美。练习吧!”
输出:[[“练习”,“ 3”],[“完美”,“ 2”], [“ makes”,“ 1”],[“ youll”,“ 1”],[“ only”,“ 1”], [“ get”,“ 1”],[“ by”,“ 1”],[“ just”,“ 1”]]
我的想法:
我想做的第一件事是首先获取不带标点的字符串,并将所有字母都小写成字符串向量。然后,我使用了unordered_map
容器来存储字符串和它的出现次数。卡住的地方是创建一个自定义比较器,以确保如果我有一个具有相同计数的字符串,那么我将根据它在实际给定字符串中的优先级对其进行排序。
代码:
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <sstream>
#include <iterator>
#include <numeric>
#include <algorithm>
using namespace std;
struct cmp
{
bool operator()(std::string& word1,std::string& word2)
{
}
};
vector<vector<string>> wordCountEngine( const string& document )
{
// your code goes here
// Step 1
auto doc = document;
std::string str;
remove_copy_if(doc.begin(),doc.end(),std::back_inserter(str),std::ptr_fun<int,int>(&std::ispunct));
for(int i = 0; i < str.size(); ++i)
str[i] = tolower(str[i]);
std::stringstream ss(str);
istream_iterator<std::string> begin(ss);
istream_iterator<std::string> end;
std::vector<std::string> vec(begin,end);
// Step 2
std::unordered_map<std::string,int> m;
for(auto word : vec)
m[word]++;
// Step 3
std::vector<std::vector<std::string>> result;
for(auto it : m)
{
result.push_back({it.first,std::to_string(it.second)});
}
return result;
}
int main() {
std::string document = "Practice makes perfect. you'll only get Perfect by practice. just practice!";
auto result = wordCountEngine(document);
for(int i = 0; i < result.size(); ++i)
{
for(int j = 0; j < result[0].size(); ++j)
{
std::cout << result[i][j] << " ";
}
std::cout << "\n";
}
return 0;
}
如果有人可以帮助我学习如何为此代码构建自定义比较器,我将不胜感激。