logo Homepage
+  NewbieContest
|-+  Général» Defouloir» Algo du soir, Bonsoir !
Username:
Password:
Pages: 1 [2]
  Imprimer  
Auteur Fil de discussion: Algo du soir, Bonsoir !  (Lu 12998 fois)
harvey

Profil challenge

Classement : 12/54254

Membre Senior
****
Hors ligne Hors ligne
Messages: 316


Voir le profil WWW
« #15 le: 22 Mars 2017 à 23:40:01 »

Joli, pixis. Effectivement, ça devient simple quand on se rend compte qu'on n'introduit pas de faux négatif en retirant un sous-ensemble sans élément strictement majoritaire. Et qu'il y a au plus deux éléments à recompter à la fin dans le pire des cas (de la manière dont j'interprète l'énoncé, en tout cas).
On peut aussi éviter le test en début de fonction (ça ne change pas grand chose):
Code:
#encoding=utf8
def maj2(liste):
    N = len(liste)
    if N==0:
        return -1
    cpt = 0
    for element in liste:
        if cpt == 0:
            candidat = element
        if candidat == element:
            cpt += 1
        else:            
            cpt -= 1
    
    #cas cpt > 0:
    #seule l'élément majoritaire de la dernière sous-séquence
    #peut être majoritaire globalement
    if cpt > 0:
        if liste.count(candidat)*2 >= N:
            return candidat
        return -1
    #cas cpt == 0:
    #la longueur de la liste est paire
    #il n'y a pas d'élément strictement majoritaire
    #il suffit de tester si le dernier candidat et le dernier élément
    #de la liste (qui sont différents) sont majoritaires
    count1 = liste.count(candidat)
    count2 = liste.count(liste[-1])
    if count1 == count2:
        return -1
    elif count1*2 >= N:
        return candidat
    elif count2*2 >= N:
        return liste[-1]
    return -1
« Dernière édition: 22 Mars 2017 à 23:44:53 par harvey » Journalisée

L'entropie vient en mangeant.
BAAL

Profil challenge

Classement : 13/54254

Membre Héroïque
*****
Hors ligne Hors ligne
Messages: 532


Voir le profil
« #16 le: 23 Mars 2017 à 04:42:06 »

Bien joué à vous trois! Alkanor a donné la bonne approche en premier, mais sans code, et on dirait que pixis avait trouvé avant mais sans finaliser proprement. Enfin bref... C’était bien ça!
Voici l’algo en question, avec une belle illustration:
https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_vote_algorithm

Pour répondre à vos questions sur la complexité spatiale:

>>>> Edit : d'ailleurs par rapport à la complexité spatiale, est-ce qu'on considère que modifier le tableau initial (chaque case) génère une  complexité spatiale O(n) ou bien on reste en O(1) ? (dans le premier cas d'ailleurs le tri serait alors en O(n) spatialement)

Ça dépend: s’il est permis de modifier le tableau donné, vu que tu peux le trier sur place (e.g. quicksort), la complexité spatiale est O(1). Mais dans ce problème je crois qu’il est plus rigoureux de supposer que le tableau donné ne peux être modifié, auquel cas tu dois créer un autre tableau pour sauver la version triée: Ça donne donc une complexité O(N).

>>>> edit : Ah bah oui je peux le faire sans récursion et là c'est O(n) temps et 0(n) espace (sauf que je pense pas avoir compris la complexité espace, ya forcément besoin de O(n) pour une liste de longueur n non ?)

Non, la complexité de ton algo dépend de l’espace additionel que tu génères, le tableau donné ne compte pas. Si à chaque itération tu ne fais que sauver une variable, c’est O(1). Si par contre tu crées un tableau de N éléments, c’est O(N), mais il n’y en a pas besoin ici comme tu as bien vu.
Si O(N) espace était permis, je crois que la solution la plus évidente serait d’avoir un compteur pour chaque nombre qu’on lit, puis de passer à travers tous les compteurs et de voir lequel est le plus grand.
Journalisée
pixis
Administrateur

Profil challenge

Classement : 16/54254

Membre Héroïque
*****
Hors ligne Hors ligne
Messages: 664


Voir le profil WWW
« #17 le: 23 Mars 2017 à 07:55:20 »

Ah bah l'algo a le même soucis que moi, ça ne marche que pour des majorités strictes

Citation
Initialize an element m and a counter i with i = 0
For each element x of the input sequence:
    If i = 0, then assign m = x and i = 1
    else if m = x, then assign i = i + 1
    else assign i = i − 1
Return m


input = [2,3,4,2] => On va avoir
Cycle 1 : m = 2 et i = 1
Cycle 2 : m= 2 et i = 0
Cycle 3 : m = 4 et i = 1
Cycle 4 : m = 4 et i = 0

Ca va donc retourner 4 et voir que ce n'est pas majoritaire, donc ça donnera -1.

Mais avec la technique d'harvey, on s'en sort
Journalisée

Newbie Contest Staff :
Pixis
Statut :
Administrateur
Blog :
hackndo
Pages: 1 [2]
  Imprimer  
 
Aller à: