Znajdź liczbę powtórzonych podbarw w tablicy

Question

Istnieje tablica indeksowana od 0-n (tj. Size = n) zawierająca elementy z 0-m, gdzie m < n (załóżmy, że m jest 100 lub 1000 razy mniejsza niż n, m jest znacznie mniejsza niż n) , tak wiele elementów lub podelementów musi zostać powtórzonych i musimy znaleźć liczbę takich powtórzonych podelementów o rozmiarze 1 lub większym niż 1. Na przykład, rozważ tablicę o rozmiarze 1 lub większym niż 1. Na przykład, rozważ tablicę o rozmiarze 1 lub większym niż 1. Na przykład, rozważ tablicę , tutaj 2 Powtarza się 1 raz 4 Powtarza się 1 raz
5 jest powtarzany 1 raz
1 2 jest powtarzany 1 raz
2 4 jest powtarzany 1 raz
4 1 jest powtarzany 1 raz
1 2 4 jest powtarzany 1 raz
2 4 1 jest powtarzany 1 raz
1 2 4 1 jest powtarzany 1 raz
Tak więc ostateczna odpowiedź jest sumą tych, tj. 11
Czy ktoś może zaproponować pewną strukturę danych lub skuteczny algorytm do rozwiązania tego problemu. Myślałem o haszowaniu m i zwracając uwagę na wartość indeksu, gdzie występuje, ale nie sformalizowałem go.
Załóżmy n,m < 10^5

Answer 1

1. Utwórz skrót, który zawiera liczby całkowite jako klucze, a listy rozszerzalne (połączone listy) na przykład liczby całkowite jako wartości.

2. Przeczytanie listy wprowadzania. Traktuj każdy element wejściowy, który jest skanowany jako klucz; dołącz indeks następującego elementu do powiązanej listy wartości.

3. Teraz powtarzana liczba 1-elementowa to n - | klucze |

4. Następnie przejdź przez klawisze. Dla każdego klucza traktuj indeksowane elementy oryginalnej listy jako nową listę wejściową. Utwórz nowy skrót i kontynuuj jak w kroku 1.Zwróć uwagę, że kiedy przechowujemy indeksy, nadal używamy tych z oryginalnej listy.

Przykład: 1 2 4 1 2 4 1 5 6 3 5 (Załóżmy, że indeksujemy od zera). Tutaj, n = 11.

• 1 -> [1, 4, 7]
• 2 -> [2, 5]
• 3 -> [10]
• 4 -> [3, 6]
• 5 -> [8 nil]
• 6 -> [9]

Liczba powtarzających 1-ELT wynosi 11 - 6 = 5.

Teraz przechodzimy przez klawisze. Zaczynamy od 1. Lista indeksów to [1, 4, 7], która odpowiada elementom [2, 2, 5].

• 2 -> [2, 5]
• 5 -> [8]

ten wybiera się 3 - 2 = 1 duplikat listy 2-elementu.

etc ...

Czas trwania: Linear na wejście + wyjście

Answer 2

Użyłem podejścia opartego na drzewach przyrostków, od Skienna's book on the design of algorithms. Drzewa przyrostków są szczególnym rodzajem trie tree, w którym każdy sufiks danego ciągu wstawia się do drzewa trie. Drzewa Trie są sposobem przechowywania wielu słów w jednym drzewie: korzeń jest ciągiem zerowym, a każda krawędź dodaje znak. Poniżej przedstawiłem bardzo prostą implementację jako dowód koncepcji.

#include <iostream> 
#include <string> 
using std::string; 
using std::cout; 

class Node 
{ 
    Node* m_descendants[10]; 
    int m_count; 
public: 
    Node() 
    { 
     for(int i=0; i<10; ++i) { m_descendants[i] = nullptr; } 
     m_count = 0; 
    } 
    void Add(const char* str) { 
     // Increment number of times we've reached this node 
     m_count++; 

     const int firstDigit = str[0] - '0'; 
     if (!(0 <= firstDigit && firstDigit <= 9)) return; // recursion base case 

     // Access descendant node correponding to current digit 
     Node*& descendant = m_descendants[firstDigit]; 
     if (descendant == 0) { // create descendant if necessary 
      descendant = new Node; 
     } 

     // Recurse on rest of string 
     descendant->Add(str +1); 
    } 
    void Print(const string& str, int countAdj=0) const // debug function 
    { 
     for(int nextDigit=0; nextDigit<10; ++nextDigit) { 
      const Node* node = m_descendants[nextDigit]; 
      if (node) { 
       const int adjustedCount = node->Count() - countAdj; 
       if (adjustedCount > 0) { 
        char c = '0' + nextDigit; 
        string strWithC = str; 
        strWithC += c; 
        cout << strWithC << ": " << adjustedCount << "\n"; 
        node->Print(strWithC, countAdj); 
       } 
      } 
     } 
    } 
    int SumRepeated() const 
    { 
     int sumRepeated = 0; 
     for(int nextDigit=0; nextDigit<10; ++nextDigit) { 
      const Node* node = m_descendants[nextDigit]; 
      if (node) { 
       const int repeatCount = node->Count() -1; 
       if (repeatCount > 0) { 
        sumRepeated += repeatCount; 
        sumRepeated += node->SumRepeated(); 
       } 
      } 
     } 
     return sumRepeated; 
    } 
    int Count() const { return m_count; } 
}; 

int main(int argc, const char* argv[]) 
{ 
    // Construct 
    Node* const root = new Node; 
    for(const char* str = "12412415635"; *str; ++str) { 
     root->Add(str); 
    } 

    // Print 
    root->Print(string(), 1); 

    cout << "Sum repeated is " << root->SumRepeated() << "\n"; 

    return 0; // (nodes are leaked) 
} 

Wyjście

1: 2 
12: 1 
124: 1 
1241: 1 
2: 1 
24: 1 
241: 1 
4: 1 
41: 1 
5: 1 
Sum repeated is 11 

Uwaga istnieje jeden dodatkowy podciąg tutaj powtarzane, czyli 1241

Jak powiedziałem, jest to dowód koncepcji, tak, na przykład, że chcesz używać słownika zamiast tablicy do przechowywania potomków, z większym m. Również ta implementacja nie jest optymalna, nawet jeśli chodzi o ogólny algorytm: jest to O (n^2) w czasie i przestrzeni. Możesz optymalizować przez zwijanie ścieżek bez rozgałęzień, aby uzyskać przestrzeń O (n), i użyć sprytnych algorytmów konstrukcyjnych, aby uzyskać czas O (n). Ponadto, jak wskazano w jednej z pozostałych odpowiedzi, nie trzeba przetwarzać pod-ciągów, które są do połowy długości oryginału.

Answer 3

Oto coś w JavaScript: (wyjście jest bardziej lub mniej bezpośredni i JavaScript jest jednym z najwolniejszych, myślę):

<script> 

function f (s, m) { 
    var i = 0, n = s.length, c = 0, H = {}, Hi = {} 
    while (i < n-1) { 
    for (var j=i+1; j<=Math.min (i + 1 + m,n - 1); j++) { 
     if (s[i] == s[j]) { 
     var i_= i, j_= j, tmp = '' 
     while (s[i_] == s[j_] && i_ < j) { 
      tmp += String (s[i_]) 
      i_++ 
      j_++ 
     } 
     var k = tmp.length - 1 
     while (k >= 0) { 
      if (!H[tmp]) { 
      H[tmp] = 1 
      Hi[tmp] = i 
      c++ 
      } 
      else if (i == Hi[tmp]) { 
      H[tmp]++ 
      c++ 
      } 
      tmp = tmp.substr(0,k--) 
     } 
     } 
    } 
    i++ 
    } 
    var t1 = '' 
    for (var i in H) t1 += i + ", " 
    return [t1,c] 
} 

var a1 = [1,2,4,1,2,4,1,5,6,3,5], 
    a2 = [] 

for (var i=0;i<100000;i++) a2.push(Math.floor(Math.random()*10)) 

console.log(a1 +"\n"+ f(a1,10)) 
console.log(f(a2,10)) 

</script> 

wyjściowa:

1,2,4,1,2,4,1,5,6,3,5 
1, 2, 4, 5, 12, 24, 41, 124, 241, ,10 

["0...6358, 3582, 038, 4304, 2068, 095, 
9252, 37866, 3786, 7866, 7893, 8701, 0669, ", 771]