如何在C++中找到重复元素的索引？

Question

C++中是否有任何STL函数允许我在数组中查找重复项的所有索引？

例如:

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

应该返回0,1

Answer 1

有效地,您可以使用a 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; where k是数组中的元素A,并且v是数组中该元素的索引.

• 对于每个项目,在数组中a包含索引i:

  • 找到kv是否a存在k于dup
  • 如果存在,
    • 插入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

如果您需要按顺序索引,则可以简单地对结果数组进行排序.