c++ - 在c ++中找到两个向量中第一个公共条目的位置的最快方法是什么？

Question

我有两个向量u = {32, 25, 13, 42, 55, 33}，v = {18, 72, 53, 39, 13, 12, 28}我想确定它们的第一个公共条目的位置，13。对于这些示例向量，这些位置是 3 和 5。找到这些位置的最快方法是什么？我必须多次执行此操作。

Answer 1

假设您没有重复，您可以使用以下内容：

std::pair<std::size_t, std::size_t>
common_entry_indexes(const std::vector<int>& u, const std::vector<int>& v)
{
    const std::size_t min_size = std::min(u.size(), v.size());
    std::map<int, std::size_t> s; // might be `std::unordered_map`

    for (std::size_t i = 0; i != min_size; ++i)
    {
         if (auto [it, inserted] = s.insert({u[i], i}); !inserted) { return {i, it->second}; }
         if (auto [it, inserted] = s.insert({v[i], i}); !inserted) { return {it->second, i}; }
    }
    for (std::size_t i = min_size; i != u.size(); ++i)
    {
         if (auto [it, inserted] = s.insert({u[i], i}); !inserted) { return {i, it->second}; }
    }
    for (std::size_t i = min_size; i != v.size(); ++i)
    {
         if (auto [it, inserted] = s.insert({v[i], i}); !inserted) { return {it->second, i}; }
    }
    return {-1, -1}; // Not found
}

演示

• 重复的可能会通过额外的检查来处理。
• 复杂性应该O(max(N, M) * log(N + M))与 map （O(max(N, M))平均与std::unordered_map）

Answer 2

如果不是最快的，那么肯定是最简单的（假设，如您的问题，您想要基于 1 的索引，因此我们可以将{0, 0}其用作“未找到”信号和size_t索引的类型）：

#include <utility>   // For std::pair
#include <algorithm> // For std::find
#include <vector>
#include <iostream>

std::pair<size_t, size_t> FirstCommon(std::vector<int>& a, std::vector<int>& b)
{
    for (size_t i = 0; i < a.size(); ++i) {
        auto f = std::find(b.begin(), b.end(), a.at(i));
        if (f != b.end()) return { i + 1, f - b.begin() + 1 }; // Found a[i] in b
    }
    return { 0, 0 };
}

int main()
{
    std::vector<int> u = { 32, 25, 13, 42, 55, 33 };
    std::vector<int> v = { 18, 72, 53, 39, 13, 12, 28 };
    auto match = FirstCommon(u, v);
    std::cout << "Position is {" << match.first << "," << match.second << "}." << std::endl;
    return 0;
}

Answer 3

除了“小型向量”和“无重复”之外，如果您的密钥始终在一个小范围内（例如“没有密钥将永远大于 10.000”），那么您可以利用这些额外信息实现 O(max(N,M)) 解决方案（@Jarod 是 O(max(N,M) * log(N+M)），@Adrian 是 O(N*M)）。

首先，建立一个足够大的素数（即一个大于最大键的素数），然后开始建立一个哈希图，直到第一次发生冲突的地方。

std::pair<size_t, size_t> findFirstMatch(const std::vector<int>& u, const std::vector<int>& v, const int& prime) {
    std::vector<size_t> hashmap(prime, INT_MAX);    // ---> 'INT_MAX' returned if no common entries found.
    size_t smallerSz = std::min(u.size(), v.size());
    std::pair<size_t, size_t> solution = { INT_MAX, INT_MAX };
    bool noCollision = true;

    // Alternate checking, to ensure minimal testing:
    for (size_t i = 0; i < smallerSz; ++i) {
        //One step for vetor u:
        size_t& idx = hashmap[u[i] % prime];
        if (idx < INT_MAX) {    // ---> Collision!
            solution = { i, idx };
            noCollision = false;
            break;
        }
        idx = i;

        //One step for vector v:
        idx = hashmap[v[i] % prime];
        if (idx < INT_MAX) {    // ---> Collision!
            solution = { idx, i };
            noCollision = false;
            break;
        }
        idx = i;
    }

    //If no collisions so far, then the remainder of the larger vector must still be checked:
    if(noCollision){
        bool uLarger = u.size() > v.size();
        const std::vector<int>& largerVec = (uLarger) ? u : v;
        for (size_t i = smallerSz; i < largerVec.size(); ++i) {
            size_t& idx = hashmap[largerVec[i] % prime];
            if (idx < INT_MAX) {    // ---> Collision!
                if (uLarger) solution = { i, idx };
                else         solution = { idx, i };
                break;
            }
            idx = i; 
        }
    }
    return solution;
}

用法

int main()
{
    std::vector<int> u = { 32, 25, 13, 42, 55, 33 }, v = { 18, 72, 53, 39, 13, 12, 28 };
    const int prime = 211; // ---> Some suitable prime...

    std::pair<size_t, size_t> S = findFirstMatch(u, v, prime);
    std::cout << "Solution = {" << S.first << "," << S.second << "}." << std::endl;
    return 0;
}

它输出“{2, 4}”而不是“{3, 5}”，因为第一个索引是 0。随意修改它。