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_algorithmPour 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.