Wie finden Sie den Index doppelter Elemente in C++?

Question

Gibt es irgendeine STL-Funktion in C++, mit der ich alle Indizes von Duplikaten in einem Array finden kann?

Für zB:

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

Rückkehr sollte 0,1

Answer 1

Effizient könnten Sie eine std::unordered_set (um doppelte Indizes eindeutig zu verfolgen) und std::unordered_map (um eindeutige Zahlen und ihre Indizes zu verfolgen) verwenden.

Dies macht es in O(N * [O(1) + ... + O(1)])... etwa =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()}; 
} 

Erläuterung:

Da ein Array A

• eine Reihe von einzigartigen Indizes verwenden, rtn.

• Unter Verwendung einer KV (Schlüssel-Wert) Karte, dup; Dabei ist k ein Element im Array A und v ist der Index dieses Elements im Array.

• für jedes Element, a mit Index i im Array:

  • finden kv wenn a existiert als k in dup
  • Wenn es vorhanden ist,
    • Insert i in rtn
    • Einfügen v in rtn
  • Else, fügen a und i als kv in dup
• Rückkehr rtn

ein vollständiges Beispiel Siehe: Live on Coliru.

---

Für einen Eingang:

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

Wir haben eine Leistung von:

1 0 

Wieder

Für einen Eingang:

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

Wir haben eine Leistung von:

7 0 5 1 6 

Wenn Sie die Indizes in Auftrag benötigen, können Sie einfach das resultierende Array sortieren.

Answer 2

Ich glaube nicht, gibt es eine aus der Box STL Art und Weise, dies zu tun. Hier ist ein O (N * N) Lösung:

int array[] = {1, 2, 3, 1, 4}; 
    constexpr int size = 5; // ToDo - don't hardcode this. 
    bool duplicates[size] = {}; 

    for (std::size_t i = 0; i < size; ++i){ 
     if (!duplicates[i]){ /*No point in re-testing*/ 
      for (std::size_t j = i + 1; j < size; ++j){ 
       if (array[i] == array[j]){ 
        duplicates[i] = duplicates[j] = true; 
       } 
      } 
     } 
    } 

Ein Ansatz, der auf Sortier beweisen kann effiziente für längere Arrays: aber Sie würden eine Tabelle der neuen Position bauen müssen -> alte Position, um die Indizes zu erhalten, von die doppelten Elemente.

Answer 3

Meine zwei Cent auf diese. Nicht ganz sicher über die Big-O dieser einen aber (sieht aus wie O (N) für mich):

std::vector<std::size_t> findDuplicateIndices(std::vector<int> const & v) 
{ 
    std::vector<std::size_t> indices; 
    std::map<int, std::pair<int, std::size_t>> counts; // pair<amount, firstSeenPos> 

    for (std::size_t i = 0 ; i < v.size() ; ++i) 
    { 
     std::size_t const amount = ++counts[v[i]].first; 
     /**/ if (amount == 1) // First encounter, record the position 
     { 
      counts[v[i]].second = i; 
      continue; 
     } 
     else if (amount == 2) // Second encounter, add the first encountered position 
      indices.push_back(counts[v[i]].second); 

     indices.push_back(i); 
    } 
    return indices; 
} 

Try it online!