Trouver l'entrée la plus commune dans un tableau

Question

Vous recevez un tableau d'entiers non signés de 32 bits d'une longueur maximale de 2 ³² , avec la propriété que plus de la moitié des entrées du tableau sont égales à N, pour certaines versions 32 bits. N entier non signé. Trouvez N en regardant chaque nombre du tableau une seule fois et en utilisant au plus 2 ko de mémoire.

Votre solution doit être déterministe et vous devez être sûr de trouver N.

Answer 1

Conservez un entier pour chaque bit et incrémentez cette collection de manière appropriée pour chaque entier du tableau.

A la fin, certains bits auront un nombre supérieur à la moitié de la longueur du tableau - ces bits déterminent N. Bien sûr, le nombre sera supérieur au nombre d'occurrences de N, mais cela ne se produit pas. matière. L'important est que tout bit qui ne fait pas partie de N ne puisse pas se produire plus de la moitié des temps (car N a plus de la moitié des entrées) et tout bit faisant partie de N doit apparaît plus de la moitié des fois (car cela se produira à chaque fois que N se produit et tous les extras).

(Aucun code pour le moment - sur le point de perdre l'accès au réseau. Espérons que ce qui précède est suffisamment clair cependant.)

Answer 2

Algorithme de vote majoritaire à temps variable de Boyer et Moore ; - descendez dans le tableau en maintenant votre réponse à la question.

Answer 3

Vous pouvez le faire avec seulement deux variables.

public uint MostCommon(UInt32[] numberList)
{
    uint suspect = 0;
    int suspicionStrength = -1; 
    foreach (uint number in numberList)
    {
        if (number==suspect)
        {
            suspicionStrength++;
        }
        else
        {
            suspicionStrength--;
        }

        if (suspicionStrength<=0)
        {
            suspect = number;
        }
    }
    return suspect;
}

Faites du premier nombre le nombre suspect et continuez à parcourir la liste en boucle. Si le nombre correspond, augmentez la force de la suspicion de un; si cela ne correspond pas, réduisez d'un degré la force de la suspicion. Si la force de soupçon atteint 0, le nombre actuel devient le nombre suspect. Cela ne ne fonctionnera pas pour trouver le numéro le plus commun, mais uniquement un nombre représentant plus de 50% du groupe. Résistez à l'envie d'ajouter une vérification si suspicionStrength est supérieur à la moitié de la longueur de la liste. Des comparaisons plus totales seront toujours effectuées.

P.S. Je n'ai pas testé ce code - utilisez-le à vos risques et périls.

Answer 4

Pseudo-code (bloc-notes C ++ :-)) pour l'algorithme de Jon:

int lNumbers = (size_of(arrNumbers)/size_of(arrNumbers[0]);

for (int i = 0; i < lNumbers; i++)
  for (int bi = 0; bi < 32; bi++)
    arrBits[i] = arrBits[i] + (arrNumbers[i] & (1 << bi)) == (1 << bi) ? 1 : 0;

int N = 0;

for (int bc = 0; bc < 32; bc++)
  if (arrBits[bc] > lNumbers/2)
    N = N | (1 << bc);

Answer 5

Notez que si la séquence a0, a1,. . . , un - 1 contient un chef de file, puis après avoir retiré une paire de éléments de valeurs différentes, la séquence restante a toujours le même leader. En effet, si nous supprimer deux éléments différents, alors un seul d'entre eux pourrait être le chef. Le chef du nouvelle séquence se produit plus de n / 2 - 1 = (n - 2) / 2 fois. Par conséquent, il est toujours le chef de la nouvelle séquence d'éléments n - 2 .

Voici une implémentation Python, avec une complexité temporelle O (n):

def goldenLeader(A):
    n = len(A)
    size = 0
    for k in xrange(n):
        if (size == 0):
            size += 1
            value = A[k]
        else:
            if (value != A[k]):
                size -= 1
            else:
                size += 1
    candidate = -1
    if (size > 0):
        candidate = value
    leader = -1
    count = 0
    for k in xrange(n):
        if (A[k] == candidate):
            count += 1
    if (count > n // 2):
        leader = candidate
    return leader

Answer 6

Il s'agit d'un problème standard dans les algorithmes de transmission en continu (où vous avez un flux de données énorme (potentiellement infini)) et vous devez calculer des statistiques à partir de ce flux, en passant par ce flux une fois.

Clairement, vous pouvez l'aborder avec un hachage ou un tri, mais avec un flux potentiellement infini, vous manquez clairement de mémoire. Donc, vous devez faire quelque chose d'intelligent ici.

L'élément majoritaire est l'élément correspondant à plus de la moitié de la taille du tableau . Cela signifie que l'élément majoritaire apparaît plus que tous les autres éléments combinés ou que si vous comptez le nombre de fois, l'élément majoritaire apparaît et soustrayez le nombre total des autres éléments, vous obtiendrez un nombre positif.

Donc, si vous comptez le nombre d'un élément et soustrayez le nombre de tous les autres éléments et obtenez le nombre 0, votre élément d'origine ne peut pas être un élément majoritaire. Ceci si la base pour un algorithme correct:

Avoir deux variables, compteur et élément possible. Itérez le flux, si le compteur est à 0 - écrasez l'élément possible et initialisez le compteur, si le nombre est identique à l'élément possible - augmentez le compteur, sinon réduisez-le. Code Python:

def majority_element(arr):
    counter, possible_element = 0, None
    for i in arr:
        if counter == 0:
            possible_element, counter = i, 1
        elif i == possible_element:
            counter += 1
        else:
            counter -= 1

    return possible_element

Il est clair que l'algorithme est O (n) avec une très petite constante avant O (n) (comme 3). En outre, il semble que la complexité de l'espace soit O (1) , car nous n'avons que trois variables initialisées. Le problème est qu’une de ces variables est un compteur qui peut potentiellement devenir n (lorsque le tableau se compose des mêmes nombres). Et pour stocker le numéro n , vous avez besoin d'un espace O (log (n)) . Donc, du point de vue théorique , il s'agit de O (n) temps et de O (log (n)) . Dans la pratique , vous pouvez insérer un nombre 2 ^ 128 dans un entier long et ce nombre d'éléments dans le tableau est incroyablement énorme.

Notez également que l’algorithme ne fonctionne que s’il existe un élément majoritaire. Si un tel élément n'existe pas, il retournera quand même un nombre qui sera sûrement faux. (il est facile de modifier l’algorithme pour savoir si l’élément majoritaire existe)

Chaîne d'histoire: cet algorithme a été inventé quelque part en 1982 par Boyer et Moore et appelé Algorithme de vote à la majorité Boyer – Moore .

Answer 7

Je me souviens de cet algorithme, qui pourrait ou non suivre la règle des 2K. Il peut être nécessaire de le réécrire avec des piles et autres pour éviter de dépasser les limites de mémoire dues aux appels de fonction, mais cela peut être inutile car il n’existe jamais un nombre logarithmique de ces appels. Quoi qu’il en soit, j’ai de vagues souvenirs de collégiens ou une solution récursive à ce problème qui impliquait diviser pour régner, le secret étant que lorsque vous divisez les groupes en deux, au moins une des moitiés a toujours plus de la moitié de ses valeurs égales au max. . La règle de base lors de la division est que vous renvoyez deux valeurs top candidates, dont l'une est la valeur top et l'autre, une autre valeur (qui peut ou non être la 2ème place). J'oublie l'algorithme lui-même.

Answer 8

Preuve de l'exactitude de la réponse de buti-oxa / Jason Hernandez, en supposant que la réponse de Jason est la même que celle de buti-oxa et que les deux fonctionnent de la même manière que l'algorithme décrit:

Nous définissons la force de suspicion ajustée comme étant égale à la force de suspicion si la valeur supérieure est sélectionnée ou la force de suspension si la valeur supérieure n'est pas sélectionnée. Chaque fois que vous choisissez le bon numéro, le niveau de suspicion ajusté actuel augmente de 1. Chaque fois que vous sélectionnez un mauvais numéro, il diminue de 1 ou augmente de 1, selon que le nombre sélectionné est actuellement incorrect ou non. La force de suspicion ajustée à la fin minimale possible est donc égale au nombre de [valeurs supérieures] - nombre de [autres valeurs]