Eine interessante Google-interview Algorithmus, den ich online gefunden, die erfordert, dass die lineare Zeit

So fand ich diese Google-interview-Algorithmus Frage online. Es ist wirklich interessant, und ich habe noch nicht bis kommen mit einer guten Lösung. Bitte haben Sie einen Blick und geben Sie mir einen Tipp/Lösung, es wäre toll, wenn Sie schreiben, die code in Java :).

"Design ist ein Algorithmus, der, gegeben eine Liste von n Elementen in ein array, findet alle Elemente, die mehr als n/3 mal in der Liste.
Der Algorithmus, der ausgeführt werden soll in der linearen Zeit. (n >=0 )
Sie erwartet, dass Sie Vergleiche und erreichen die lineare Zeit. Keine Vermischung/übermäßigen Raum/und verwenden Sie keine standard-lineare Zeit-deterministische Auswahl algo"

and don't use standard linear time deterministic selection algo sagen, was???
Ich bin neugierig zu wissen, wie würde man dies tun, ohne hashing. Obwohl es ein int[] zählen als hashing. Es def zählt als übermäßigen Raum.
Ich kann nicht denken, der eine exakte Lösung von der Fledermaus, aber ich glaube, es ist ein gut bekanntes problem, das findet alle Elemente, die mehr als n/2 mal Durchlaufen das array und mit einem trick zu finden Sie die beliebtesten element dann schauen Sie durch das array wieder zu überprüfen, wenn es erscheint, oft genug. Wenn Sie wiederholen Sie diesen Prozess und ignorieren die beliebteste element, sollte dieses problem lösen, da gibt es höchstens 2 Elemente, die mehr als n/3 mal
Formuliert für die drei Elemente auftreten, die mehr als n/4 mal, aber einfach zu ändern: Algorithmus-Beschreibung

InformationsquelleAutor Newbie_code | 2011-12-02

8

Meine Lösung war inspiriert von den Tetris-Spiel.
Lösung markieren (betitelt als 'Tetrise-Prozess"):
verwenden Sie drei Schlüssel-Wert-Paare für die Buchhaltung, mit der-Taste das element, Wert die Anzahl der element. In einer Hauptschleife, wir halten höchstens 3 aktuelle verschiedene Elemente. Wenn die Anzahl der alle drei Schlüssel sind ungleich null ist, wir verringern die Grafen von und zu beseitigen alle zero-count-Taste(N), falls vorhanden. Am Ende gibt es möglicherweise oder möglicherweise nicht einige restliche Elemente. Das sind die überlebenden der Tetris-Prozess. Beachten Sie, dass es können nicht mehr als 3 Rest-Elemente. Wenn nichts übrig ist, haben wir null zurück. Sonst werden wir in einer Schleife durch die ursprünglichen n-Elemente, zählen die Anzahl der die übrigen Elemente und kehren diejenigen, deren Anzahl ist > n/3.

Hauch von Beweis:
Zeigen Sie die Korrektheit des obigen Algorithmus, beachten Sie, dass für ein element überleben muss die Tetris-Prozess oder in diesem bleiben, der Rückstand auf die Anforderung erfüllen. Um zu sehen, warum, lassen Sie bezeichnen die Anzahl der removal-Operationen wie m und die Gesamtzahl der verbleibenden Elemente r. Dann haben wir
n = 3 * m + r.
Von hier aus erhalten wir m <= n/3, weil r >= 0.
Wenn ein element nicht überleben Tetrise Prozess, der maximal auftreten kann es angezeigt ist, m <= n/3.

Zeit Komplexität O(n) Speicherplatz-Komplexität O(1).
- Der OP fragt zu Bericht alle Elemente, die auftreten, mehr als n/3 mal in der Liste. Beachten Sie, dass die Tetris-Algorithmus jedoch nicht gewährleisten alle restliche Elemente auftreten, die mehr als n/3 mal in der Liste (versuchen Sie es auf die Zeichenfolge "AADBBBBDABCC"; restliche Elemente B und C, aber B ist die einzige gewünschte element). So müssen Sie gehen Sie durch die Liste wieder nach dem Tetris-Prozess, zählt die vorkommen jedes Rest-element (es können maximal 2 restliche Elemente), und dann überprüfen, ob die Frequenz größer als n/3. Zum Glück ist die Zeit-und Raum-Komplexität bleiben unverändert.
- Sind nicht Ihre Schlüssel-Wert-Paare technisch hashing? Die Frage Staaten keine Vermischung zulässig. Ansonsten, die Dinge ein bisschen einfacher wäre.
- Dennoch ist dies eine sehr kreative Lösung, die Lob verdient, nicht nit-picking 🙂
- Ich sehe nicht, wie dieser Ansatz entspricht hashing. Können Sie mehr erklären?
InformationsquelleAutor Chivalryman
7

Tipp: Schauen Sie Boyer und Moore Lineare Zeit-Voting-Algorithmus

Besserer Hinweis: überlegen Sie sich die Lösung der meisten problem die erste. Das ist, zu versuchen, ein element, das Auftritt, zumindest n/2 Zeiten. Die Grundidee des Algorithmus ist, wenn wir Abbrechen jedes vorkommen eines Elements e mit allen anderen Elementen, die Verschieden sind von e dann e wird bestehen, bis am Ende, wenn es die Mehrheit der element.
```
findCandidate(a[], size)
    //Initialize index and count of majority element
    maj_index = 0;
    count = 1;

    for i = 1 to n–1 {
      if a[maj_index] == a[i]
          count++;
      else
          count--;

      if count == 0 {
          maj_index = i;
          count = 1;
      }
    }
    return a[maj_index]
```
Dieser Algorithmus iteriert über alle element und unterhält eine Zählung von a[maj_index]. Wenn das nächste element ist gleich danach Schritten die zählen, wenn das nächste element nicht gleichen, dann dekrementiert die Zählung, und wenn die Anzahl 0 erreicht, dann ändert sich die maj_index dem aktuellen element und setzt die Anzahl auf 1.

Als Nächstes müssen Sie überprüfen, dass dieses element in der Tat tritt mindestens n/2 mal, aber das kann in einem Durchgang erledigt werden.
- Guter Tipp. Nicht sicher, genau, wie gelten für n/3 noch nicht, aber definitiv gut zu wissen, dass Algorithmus. Danke! Werde versuchen zu kommen mit einer Lösung zu n/3. Warum aber wurde diese Frage geschlossen? Ich denke, das ist eine gute Frage, zu lernen....
- Ich denke, es war die Art, wie Sie formuliert die Frage. Im Allgemeinen, SO sollten Sie zeigen, einige Mühe auf die Lösung der Frage selbst, sondern als Fragen der community zum schreiben von code für Sie. Ich stimmte zu, öffnen Sie es erneut.
- Um die n/3 Fall, denken Sie nur ein wenig darüber, wie dieser Algorithmus funktioniert. Es ist nicht allzu schwer zu verallgemeinern, aber ich werde Sie warnen, dass der schwierige Teil IMO ist, dass 2 unterschiedliche Elemente funktionieren könnte.
- Ich stellte diese Frage hier nur weil ich denke, dass es interessant und schwer, und ich möchte es teilen, um alle anderen, die gerne diskutieren, und wissen, wie es zu lösen. Es könnte leicht gelöst werden, mit hashing, aber w/o und in der linearen Zeit? Hmm... ich bin mir sicher, dass wer auch immer deine Antwort gelesen wird, etwas lernen, wenn Sie nicht wissen, diese vor.
- Ich bin sehr vertraut mit den Meisten Voting-Algorithmus, aber ich bin mir nicht sicher, ich sehe wie man sich hier. Die Korrektheit Beweis hängt ein lemma, das sagt, dass Sie können die Anordnung der Elemente des Arrays, so dass Sie-pair-Mädchen die Mehrheit-element in einer Weise, bricht alles andere. Dieses lemma schlägt fehl, wenn Sie auf der Suche nach einem element, das erscheint, ein Drittel der Zeit. Können Sie ein bisschen genauer darüber, wie Sie verallgemeinern den Algorithmus?
- Sie müssen nur zählen die nicht e Elemente als 0,5 und zählen e als 1.0 zu machen, es klappt, obwohl diese nur fangen, eines der beiden Elemente. Ich werde fügen Sie die details, wenn diese wieder geöffnet.
- Was ist mit der Sequenz BAACAABAACAA...? Nicht Einem niemals den match-element? Bin ich Missverständnis der Vorschlag?
- Ein mehr Tipp: es sind höchstens 2 solcher Elemente.
- Ich Stimme mit @templatetypedef. Ich denke, Chivalryman die Tetris-Ansatz ist ein sehr besseren Weg, um dieses problem zu lösen, als eine Anpassung der Mehrheit.
- Für die Sequenz "ABADC", A ist das gewünschte element, aber die Mehrheit Algorithmus würde nicht Rendite diese. Ich Stimme mit @templatetypedef, dass der Boyer-Moore-Voting-Algorithmus kann verallgemeinert werden, um dieses problem zu lösen.
InformationsquelleAutor PengOne

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.