Algorithmes | élément majoritaire

Question

Je tente d'écrire un algorithme pour renvoyer true si un élément majoritaire existe dans un tableau et false dans le cas contraire. edit: je ne peux dire que si deux éléments sont égaux. ce qui signifie que je ne peux pas utiliser < ou>, only =. edit: la solution devrait être dans une méthode de division et de conquête. son exécution sur nlogn aller shouldnt, et je l'ai écrit quelque chose en java, mais je ne suis pas sûr si elle est correcte et comment calculer le temps d'exécution .. voici ce que je suis:

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

L'exécution de l'algorithme décrit est O(n^2). La boucle externe est exécutée n/2 fois, ainsi le compteur interne j est réinitialisé n/2 fois, et ainsi la boucle interne est exécutée au total de O(n^2) fois.

Je ne suis pas sûr que je suis la logique derrière votre idée, mais voici deux approches comment je mettre en œuvre [en pseudo-code de haut niveau]:

(1) créer un histogram de la données:

• créer un Map<Integer,Integer> [la clé est l'élément et la valeur est le nombre de occurances]
• itérer le tableau, et pour chaque élément compte combien de fois il semble
• itérer l'histogramme et trouver s'il y a un maximum unique.
• S'il existe - retour vrai, sinon retour faux.

Cette approche est moyenne de O(n) si vous utilisez un HashMap comme carte.

(2) de tri et de trouver Max occurances:

• trier le tableau - à la suite, tous les éléments sont égaux à côté de l'autre. Vous pouvez utiliser Arrays.sort(array) pour le tri.
• Comptez le nombre de fois que chaque élément apparaît [similaire à l'idée de l'histogramme], et déterminez s'il existe un maximum unique. Vous n'avez pas besoin de maintenir les données pour tous les éléments, il suffit de maintenir pour le top 2, et à la fin pour voir si elles sont identiques.

Cette solution est O(nlogn) moyenne + pire des cas [en fait, selon le genre - merge sor vous donne t O(nlogn) pire des cas, alors que quick-sort vous donne O(n^2) pire des cas, et les deux sont O(nlogn) le cas moyen].

EDIT:

j'ai mal compris le problème à portée de main, je pensais que vous cherchez s'il y a un maximum unique. Ces 2 solutions conviennent toujours au problème, il suffit de modifier la dernière étape de chaque [pour vérifier si l'élément le plus courant apparaît plus de la moitié des fois, ce qui est encore assez facile et faisable dans O(n)].

De plus, il existe une autre solution: Utilisez selection algorithm pour trouver la médiane, et après l'avoir trouvé, vérifiez s'il s'agit d'un élément majoritaire et revenez si c'est le cas. Puisque l'algorithme de sélection est une solution basée sur la division et la conquête, je pense que cela correspond à vos besoins.

Answer 2

Voici un O solution Find Majority Element

Answer 3

Un élément majoritaire dans une matrice A [] de taille n est un élément qui apparaît plus de n/2 fois

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