Trouvez un élément de la liste qui apparaît au moins 60% du temps en utilisant l'approche Diviser et Conquérir ?

Question

L'entrée est un tableau qui a au plus un élément qui apparaît au moins 60 % du temps. Le but est de trouver si ce tableau a un tel élément et si oui, trouver cet élément. J'ai trouvé une fonction "diviser pour régner" qui trouve un tel élément.

from collections import Counter

def CommonElement(a):
    c = Counter(a) 
    return c.most_common(1) #Returns the element and it's frequency

def func(array):
    if len(array) == 1:
        return array[0]

    mid = len(array)//2

    left_element = func(array[:mid])
    right_element = func(array[mid:])

    if left_element == right_element:
        return right_element

    most_common_element = CommonElement(array)

    element_count = most_common_element[0][1] #Getting the frequency of the element
    percent = element_count/len(array)
    if percent >= .6:
        return most_common_element[0][0] #Returning the value of the element
    else:
        return None

array = [10,9,10,10,5,10,10,10,12,42,10,10,44,10,23,10] #Correctly Returns 10
array = [10,9,10,8,5,10,10,10,12,42,10,12,44,10,23,5] #Correctly Returns None

result = func(array)
print(result)

Cette fonction fonctionne mais elle est en O(n log(n)). Je veux implémenter un algorithme qui soit en O(n)

La fonction de récursion de mon algorithme est T(n) = 2T(n/2) + O(n). Je pense que le but est d'éliminer le besoin de trouver la fréquence, ce qui prend O(n). Des idées ?

Answer 1

Vous pouvez créer un compteur de fréquence pour tous les éléments de la liste une fois en O(n). Ensuite, itérer la table de consultation et voir si l'un d'entre eux est au moins 60% des éléments (en d'autres termes, count / len(lst) >= 0.6 ).

>>> from collections import Counter
>>> L = [4, 2, 3, 2, 4, 4, 4]
>>> Counter(L)
Counter({4: 4, 2: 1, 3: 1})
>>> Counter(L).most_common(1)
[(4, 4)]
>>> item, count = Counter(L).most_common(1)[0]
>>> count / len(L)
0.6666666666666666
>>> count / len(L) >= 0.6
True

Diviser pour mieux régner est une approche créative, mais inappropriée, pour ce problème.

... ou du moins c'est ce que je pensais, mais voyez... cette réponse .

Answer 2

Si vous avez la garantie d'avoir une liste dont 60 % des membres sont un nombre donné, ce nombre est garanti comme étant la médiane. Pour le constater intuitivement, triez la liste. Le nombre en question représente une fenêtre contiguë qui représente 60% de la longueur de la liste. Il n'y a aucun moyen de placer cette fenêtre de façon à ce qu'elle ne recouvre pas le milieu.

Il existe de nombreux algorithmes de division et de conquête pour trouver la médiane. L'un des plus courants est appelé introselect. Vous pouvez trouver une implémentation dans la bibliothèque numpy partition y argpartition fonctions (il est écrit en C). L'idée de base est de faire un quicksort, mais de ne récursionner que dans la partie qui contient l'index qui vous intéresse. Cela réduit l'algorithme à O(n).

À propos, vous pourriez rechercher n'importe quel indice entre 40 et 60 % de la longueur de la liste. 50% semble être un juste milieu raisonnable.

Pour vérifier que la médiane apparaît > 60 % du temps, exécutez une seule boucle sur le tableau, en comptant le nombre de fois où la médiane apparaît.

Answer 3

Il existe un algorithme assez simple pour trouver l'élément majoritaire d'une collection, si la collection en possède un :

def majority(l):
    count, candidate = 0, None
    for element in l:
        if count == 0:
            count, candidate = 1, element
        elif element == candidate:
            count += 1
        else:
            count -= 1
    return candidate

Cet algorithme apparie essentiellement chaque élément de l'entrée avec un autre élément ayant une valeur différente jusqu'à ce que tous les éléments non appariés aient la même valeur, puis renvoie cette valeur. Si l'entrée comporte un élément majoritaire, l'algorithme doit le renvoyer.

Vous pouvez calculer un candidat avec cet algorithme, puis faire un autre passage par l'entrée et voir si ce candidat est une supermajorité de 60%. Cet algorithme fonctionne en O(1) d'espace et O(n) de temps sans modifier l'entrée, alors que les algorithmes basés sur le hachage ou l'introselect nécessitent plus d'espace ou modifient l'entrée. Il est également immunisé contre les attaques par collision de hachage (contrairement à Counter et d'autres approches basées sur le hachage) et n'exige pas que les éléments aient une relation d'ordre (contrairement à introselect).