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

Demo

可能会通过额外检查处理重复项。
地图的复杂度应该是 O(max(N, M) * log(N + M))（而 std::unordered_map 的平均复杂度应该是 O(max(N, M))）

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's 是 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){
        const 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 << "}.";
    return 0;
}

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

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

What is the fastest way to find the positions of the first common entry in two vectors in c++?

c++

search

vector

lowest-common-ancestor