Effizienter Algorithmus, um Master-Element in einem Array zu finden?

Question

Ich versuche herauszufinden, ob ein gegebenes Array A mit N ganzen Zahlen ein "Master-Element" hat. Das Master-Element dieses Arrays ist ein Element, das im Array mehr als n/2 Mal vorkommt.

Zum Beispiel:

• das Array A={5,1,3,5,5} hat ein Master-Element (in diesem Fall 5).
• das Array A={5,1,2,3,3} hat kein Master-Element.

Unten ist mein Code so weit.

Ich würde gerne wissen, was ist der effizienteste Algorithmus, um dieses Problem zu lösen?

Der Algorithmus muss true zurückgeben, wenn das Array ein Masterelement hat und false zurückgibt, wenn es kein Masterelement hat.

boolean masterElement(int[] a) { 
    int count = 0; 
    boolean check = false; 
    for (int i = 0; i < a.length/2; i++) { 
     for (int j = 0; j < a.length; j++) { 
      if (a[i] == a[j]) { 
       count++; 
      } 
     } 
     if (count >= a.length/2) { 
      check = true; 
      break; 
     } 
     count = 0; 
    } 
    return check; 
} 

Answer 1

In Java 8, könnten Sie Streams und Collectors wie folgt verwenden:

int[] a = {5,1,3,5,5}; 
    final int n=a.length; 
    Map<Integer, List<Integer>> x = Arrays.stream(a).boxed().collect(Collectors.groupingBy(i->i)); 
    // System.out.println(x); // {1=[1], 3=[3], 5=[5, 5, 5]} 
    x.forEach((k,v)->{ 
     if(v.size()>n/2) System.out.println(k); // Check whether you need > or >= 
    }); 

Betrachten Sie bitte den Erläuterungen in den Kommentaren im Code oben.

Answer 2

boolean masterElement(int[] a) { 
    int half = a.length/2; 
    for (int i = 0; i < half; i++) { 
     int count = 1; 
     for (int j = i + 1; j < a.length && count <= half; j++) { 
      if (a[i] == a[j]) { 
       count++; 
      } 
     } 
     if (count > half) { 
      return true; 
     } 
    } 
    return false; 
}