计数共时序列向量c++

I have a sorted vector of strings, I am trying to find the coocurrence of every element in the vector:

我有一个有序的弦向量，我试图找到向量中每个元素的共时性:

V = {"AAA","AAA","AAA","BCA",...}

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

The complexity is O(n^2) right? THis is taking so much time how can I find a way to solve it?

复杂度是O(n ^ 2)对吗?这要花很多时间我怎么才能找到解决它的方法呢?

Thank you,

谢谢你！

That's the edit:

编辑:

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

2 个解决方案

#1

Not tested. I assume that the vector contains at least one element.

不测试。我假设这个向量至少包含一个元素。

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;

This is clearly O(n). There is a slight difference from your code: each word is printed only once.

这显然是O(n)。与您的代码略有不同:每个单词只打印一次。

#2

Tested, O(n), works even if the vector is not sorted or if it's empty:

被测试的O(n)即使向量不是排序的，或者是空的，也可以工作:

#include <iostream>
#include <vector>
#include <unordered_map>

int main()
{
    std::vector<std::string> v = { "aaa", "abc", "aaa", "def", "aaa", "aaa", "abc", "ghi" };
    std::unordered_map<std::string, int> m;

    for (std::vector<std::string>::iterator it = v.begin(); it != v.end(); it++)
        m[*it]++;

    for (std::unordered_map<std::string, int>::iterator it = m.begin(); it != m.end(); it++)
        std::cout << it->first << " -> " << it->second << std::endl;

    return 0;
}

Or, the appropriate snippet re-written using range-based loops for the sake of readability (thanks Frerich Raabe):

或者，为了可读性起见，使用基于范围的循环重写适当的代码片段(谢谢Frerich Raabe):

for (const auto it: v)
    m[it]++;

for (const auto it: m)
    std::cout << it.first << " -> " << it.second << std::endl;

#1