Algorithmes | élément majoritaire

Question

J'essaie d'écrire un algorithme qui renvoie vrai si un élément majoritaire existe dans un tableau et faux sinon. edit : je ne peux dire que si deux éléments sont égaux. ce qui signifie que je ne peux pas utiliser < ou >, seulement =. edit : la solution devrait être dans une méthode diviser-et-conquer. son temps d'exécution ne doit pas dépasser nlogn, et j'ai écrit quelque chose en java mais je ne suis pas sûr que ce soit correct et comment calculer le temps d'exécution Voici ce que j'ai obtenu :

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

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

Je ne suis pas sûr de suivre la logique de votre idée, mais voici deux approches de sa mise en œuvre [en pseudo-code de haut niveau] :

(1) créer un histogramme à partir des données :

• créer un Map<Integer,Integer> [la clé est l'élément et la valeur est le nombre d'occurrences].
• itérer le tableau, et pour chaque élément compter combien de fois il apparaît.
• itérer l'histogramme et trouver s'il y a un maximum unique.
• S'il y en a un - retournez le vrai, sinon retournez le faux.

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

(2) trier et trouver les occurrences maximales :

• Trier le tableau - comme résultat, tous les éléments égaux sont adjacents les uns aux autres. Vous pouvez utiliser Arrays.sort(array) pour le tri.
• Comptez le nombre de fois où chaque élément apparaît [similaire à l'idée de l'histogramme], et trouvez s'il existe un maximum unique. Vous n'avez pas réellement besoin de gérer les données pour all éléments, il suffit de maintenir pour les 2 premiers, et à la fin de voir s'ils sont identiques.

Cette solution est O(nlogn) la moyenne + le pire des cas [en fait, selon le type d'entreprise]. fusionner les sortis t vous donne O(nlogn) dans le pire des cas, alors que tri rapide vous donne O(n^2) le pire des cas, et les deux sont O(nlogn) sur un cas moyen].

EDIT :

J'ai mal compris le problème, je pensais que vous cherchiez s'il y avait une Maxima 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 fréquent apparaît plus de la moitié du temps, ce qui est encore une fois assez facile et faisable en O(n) ].

Il existe également une autre solution : Utilisez algorithme de sélection pour trouver la médiane, et après l'avoir trouvée, vérifier si c'est un élément majoritaire, et retourner si c'est le cas. L'algorithme de sélection étant une solution basée sur le principe du diviser pour régner, je pense qu'il répond à vos besoins.

Answer 2

Un élément majoritaire dans un tableau 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;
}

Answer 3

Voici une solution O(n) Trouver l'élément majoritaire