count co-ocurrence sorted vector string c ++

Question

我有一个排序的字符串向量,我试图找到向量中每个元素的共存:

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
         }
}

Answer 1

没有测试过.我假设向量包含至少一个元素.

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).与您的代码略有不同:每个单词只打印一次.