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

Question

我有两个 vector u = {32, 25, 13, 42, 55, 33}和 v = {18, 72, 53, 39, 13, 12, 28}我想确定它们的第一个公共(public)条目的位置，13。对于这些示例 vector ，这些位置是 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))与 map (和 O(max(N, M)) 平均与 std::unordered_map )