我有一个排序的字符串 vector ,我试图找到 vector 中每个元素的同现:
V = {"AAA","AAA","AAA","BCA",...}
int main()
{
vector<string> vec;
//for every word in the vector
for(size_t i = 0; i < vec.size();i++)
{
int counter = 0;
//loop through the vector and count the coocurrence of this word
for(size_t j = 0; j < vec.size();j++)
{
if(vec[i] == vec[j]) counter +=1;
}
cout << vec[i] << " "<<counter <<ed,l
}
}
复杂度是 O(n^2) 对吗?这要花这么多时间我怎么能找到解决它的方法?
谢谢,
这就是编辑:
int main()
{
vector<string> vec;
//for every word in the vector
for(size_t i = 0; i < vec.size();i++)
{
int counter = 0;
//loop through the vector and count the coocurrence of this word
for(size_t j = i+1; j < vec.size()-1;j++)
{
if(vec[i] == vec[j]) counter +=1;
}
cout << vec[i] << " "<<counter <<ed,l
}
}
最佳答案
未经测试。我假设 vector 至少包含一个元素。
counter = 1
for(size_t i = 1; i < vec.size(); i++)
{
if(vec[i] == vec[i-1]) counter +=1;
else
{
std::cout << vec[i-1] << ", " << counter << std::endl;
counter = 1;
}
}
std::cout << vec[i-1] << ", " << counter << std::endl;
这显然是 O(n)。与您的代码略有不同:每个单词只打印一次。
关于c++ - 计数共现排序 vector 字符串 C++,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17867359/