Algorithmen | Majoritätselement

Question

Ich versuche, einen Algorithmus zu schreiben, um wahr zurückzugeben, wenn ein Majoritätselement in einem Array existiert und andernfalls falsch. edit: ich kann nur sagen, ob zwei Elemente gleich sind. was bedeutet, dass ich < oder>, only = nicht verwenden kann. edit: Die Lösung sollte in einer Divide-and-Conquer-Methode sein. seine Laufzeit über nlogn gehen shouldnt, und ich schrieb etwas in Java, aber ich bin nicht sicher, ob es richtig ist, und wie die Laufzeit zu berechnen .. hier ist das, was ich habe:

public static boolean MajorityBoolean(int[] arr) { 
    int c; 
    int n = arr.length; 
    for (int i = 0; i < n; i = i + 2) { 
     System.out.println("*"); 
     if ((arr[i] == arr[(i + 1)%n]) || ((arr[i] == arr[(i - 1+n)%n]))) { 
      c = 0; 
      for (int j = 0; j < n; j = j + 1) 
       if (arr[j] == arr[i]) 
        c = c + 1; 
      if (c > n/2) 
       return true; 
     } 
    } 
    return false; 
} 

Answer 1

Die Laufzeit des beschriebenen Algorithmus ist O(n^2). Die äußere Schleife wird n/2 mal ausgeführt, somit wird der innere Zähler jn/2 mal zurückgesetzt, und somit wird die innere Schleife insgesamt O(n^2) mal ausgeführt.

Ich bin nicht sicher, ich verfolge die Logik hinter Ihrer Idee, aber hier sind zwei Ansätze, wie ich es umsetzen würde [in hohem Niveau Pseudo-Code]:

(1) erstellen histogram aus der Daten:

• erstellen Map<Integer,Integer> [der Schlüssel ist, das Element und der Wert ist die Anzahl der Vorkommen]
• iterieren das Array und für jedes Element zählen, wie oft es
• iterieren des Histogramms angezeigt wird, und Finde heraus, ob es ein einzigartiges Maximum gibt.
• Wenn es gibt - Rückgabe wahr, sonst Rückgabe false.

Dieser Ansatz ist durchschnittlich O(n), wenn Sie ein HashMap als die Karte verwenden.

(2) zu sortieren und zu max Vorkommen finden:

• sortieren das Array - als Ergebnis, alle gleich Elemente zueinander benachbart sind. Sie können Arrays.sort(array) zum Sortieren verwenden.
• Zählen Sie, wie oft jedes Element angezeigt wird [ähnlich der Histogramm-Idee], und finden Sie heraus, ob es ein eindeutiges Maximum gibt. Sie müssen nicht wirklich die Daten für alle Elemente pflegen, es ist genug für die Top-2 zu halten, und am Ende zu sehen, ob sie identisch sind.

Diese Lösung ist O(nlogn) Durchschnitt + worst case [tatsächlich je nach Art - merge sor t Sie O(nlogn) schlimmsten Fall gibt, während quick-sort gibt Ihnen O(n^2) schlimmsten Fall, und beide sind O(nlogn) im Durchschnitt Fall].

EDIT:

ich das Problem bei der Hand falsch verstanden, ich dachte, Sie schauen, ob es eine eindeutige Maximum ist. Diese 2 Lösungen passen immer noch für das Problem, Sie müssen nur den letzten Schritt jedes [ändern, um zu überprüfen, ob das am häufigsten vorkommende Element mehr als die Hälfte der Zeiten erscheint, was wiederum in O(n)] ziemlich einfach und machbar ist.

Es gibt auch eine andere Lösung: Verwenden Sie selection algorithm, um den Median zu finden, und nachdem Sie ihn gefunden haben, prüfen Sie, ob es ein Majoritätselement ist, und geben Sie es zurück. Da der Auswahlalgorithmus eine Lösung ist, die auf Teilen und Siegen basiert, denke ich, dass sie zu Ihren Bedürfnissen passt.

Answer 2

folgt ein O (n) Lösung Find Majority Element

Answer 3

Eine Mehrheit Element in einem Array A [] der Größe N ist ein Element, das mehr als n/2 Mal

public static boolean find(int[] arr, int size) { 
int count = 0, i, mElement; 
for (i = 0; i < size; i++) { 
    if (count == 0) 
     mElement = arr[i]; 
    if (arr[i] == mElement) 
     count++; 
    else 
     count--; 
} 
count = 0; 
for (i = 0; i < size; i++) 
    if (arr[i] == mElement) 
     count++; 
if (count > size/2) 
    return true; 
return false; 
}