c++ - 通过多个同时 vector 迭代将复杂度降低到 O(n)

Question

所以我有 2 个包含以下内容的字符串 vector :

tokens: name name place thing thing
u_tokens: name place thing

现在我的任务是同时循环遍历这两个 vector 并找到每个单词的出现并将其存储在第三个 vector 中。这是我所做的最小工作实现(我的任务没有提到重复项，所以我没有考虑删除它):

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main()
{
    vector<int> counts;
    vector<string> tokens;
    vector<string> u_tokens;

    tokens.push_back("name");
    tokens.push_back("name");
    tokens.push_back("place");
    tokens.push_back("thing");
    tokens.push_back("thing");
    u_tokens.push_back("name");
    u_tokens.push_back("place");
    u_tokens.push_back("thing");

    string temp;
    int temp_count = 0;
    for (int i = 0; i < tokens.size(); i++)
    {
        temp = tokens[i];
        for (int j = 0; j < u_tokens.size(); j++)
        {
            if(temp == u_tokens[j])
            {
                temp_count++;
            }
        }

        temp = tokens[i];
        for (int k = 0; k < tokens.size(); k++)
        {
            if (temp == tokens[k])
            {
                temp_count++;
            }
        }
        counts.push_back(temp_count);
        temp_count = 0;
    }

    for (vector<int>::const_iterator i = counts.begin(); i != counts.end(); ++i)
        cout << *i << "  ";
    return 0;
}

但是，我注意到，这显然具有 O(n^2) 的复杂性。我怎样才能将它减少到 O(n)？可能吗？

问候。

Answer 1

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
using namespace std;

void CountOccurences(const vector<string>& input, unordered_map<string, size_t>& occurences)
{
    for (int i = 0; i < input.size(); i++)
    {
        occurences[input[i]]++;
    }
}

int main()
{
    vector<string> tokens;
    vector<string> u_tokens;
    unordered_map<string, size_t> occurences;

    tokens.push_back("name");
    tokens.push_back("name");
    tokens.push_back("place");
    tokens.push_back("thing");
    tokens.push_back("thing");
    u_tokens.push_back("name");
    u_tokens.push_back("place");
    u_tokens.push_back("thing");

    CountOccurences(tokens, occurences);
    CountOccurences(u_tokens, occurences);

    for (auto i : occurences)
        cout << i.first << "=" << i.second << " ";
    return 0;
}

使用 std::unordered_map 作为 O(1) 访问容器来创建 O(N) 解决方案。当然是内存成本。

在线编译链接program