c++ - 如何在 C++ 中查找重复元素的索引？

Question

C++ 中是否有任何 STL 函数可以让我找到数组中所有重复项的索引？

例如:

int array[] = {1,1,2,3,4};

应该返回 0,1

Answer 1

高效地，您可以使用 std::unordered_set(以唯一地跟踪重复索引)和 std::unordered_map(以跟踪唯一编号及其指数)。

这在 O(N * [O(1) + ... + O(1)]) ...大约 = O (N):

template<typename ForwardIterator>
std::vector<int> get_duplicate_indices(ForwardIterator first, ForwardIterator last){
    std::unordered_set<int> rtn;
    std::unordered_map<int, int> dup;
    for(std::size_t i = 0; first != last; ++i, ++first){
        auto iter_pair = dup.insert(std::make_pair(*first, i));
        if(!iter_pair.second){
            rtn.insert(iter_pair.first->second);
            rtn.insert(i);
        }
    }
    return {rtn.begin(), rtn.end()};
}

解释:

给定一个数组A

• 使用一组唯一索引，rtn。

• 使用KV(键值)映射，dup；其中，k 是数组 A 中的一个元素，v 是该元素在数组中的索引。

• 对于每个项目，a 在数组中具有索引i:

  • 如果 a 在 dup 中作为 k 存在，则查找 kv
  • 如果存在，
    • 将i插入rtn
    • 将v插入rtn
  • 否则，将a 和i 作为kv 添加到dup
• 返回rtn

查看完整示例: Live on Coliru .

---

对于输入:

int array[] = {1,1,2,3,4};

我们有一个输出:

1 0

再次，

对于输入:

int array[] = {1, 1, 2, 3, 4, 1, 0, 0, 9};

我们有一个输出:

7 0 5 1 6

如果您需要按顺序排列索引，您可以简单地对结果数组进行排序。