Эффективный алгоритм для нахождения главного элемента в массиве?

Question

Я пытаюсь выяснить, имеет ли данный массив A, содержащий N целых чисел, «главный элемент». Главный элемент этого массива - это элемент, который больше чем n/2 раза в массиве.

Например:

• массив A={5,1,3,5,5} имеет главный элемент (в данном случае 5).
• массив A={5,1,2,3,3} не имеет основного элемента.

Ниже приведен мой код.

Я хотел бы знать, что является наиболее эффективным алгоритмом для решения этой проблемы?

Алгоритм должен возвращать true, если массив имеет главный элемент и возвращает false, если он не имеет главного элемента.

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

В Java 8, можно использовать Streams и Collectors так:

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 >= 
    }); 

Пожалуйста, посмотрите на объяснения в комментариях в коде выше.

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; 
}