La tâche consiste à trier les nombres négatifs et positifs d'un vecteur. Le hic, c'est que l'algorithme doit être O (n) et en place.
Ma "solution" est:
def Rearrange(arr):
neg = []
pos = []
for x in arr:
if x < 0:
neg.append(x)
else:
pos.append(x)
return neg + pos
Alors, ce que je me demande, c'est si cet algorithme est en place ou non? Je sais que les opérations de boucle et d'ajout satisfont un algorithme en place. Mais qu'en est-il de la liste qui stocke les valeurs? Utilise-t-il trop d'espace supplémentaire pour satisfaire un algorithme en place? Si tel est le cas, existe-t-il une solution simple à ce problème qui est apparent? En ce moment, je suis un peu coincé.
3 réponses
Avez-vous besoin de trier l'ensemble du tableau, ou simplement d'avoir des valeurs négatives à gauche et des valeurs positives (et 0) à droite?
Si ce que vous voulez réaliser est cette deuxième chose, alors la fonction suivante devrait fonctionner (elle fonctionne en place et c'est O (n)):
def rearrange(array):
left = 0
right = len(array) - 1
while left < right:
if array[left] >= 0 > array[right]:
array[right], array[left] = array[left], array[right]
left += 1
right -= 1
elif array[left] < 0:
left += 1
else:
right -= 1
>>> array = [-5, 6, 7, -4, 2, 0, -1]
>>> rearrange(array)
>>> array
[-5, -1, -4, 7, 2, 0, 6]
Non. Cette solution n'est pas en place. Deux nouveaux objets (listes) sont créés, que vous ajoutez continuellement selon la logique que vous avez spécifiée.
Pour autant que je sache, vous ne pouvez pas obtenir une vue sur place de vos données en utilisant uniquement la bibliothèque standard.
Si une solution sur place est importante pour vous, vous pouvez utiliser une bibliothèque tierce telle que numpy.
Si une solution O (n) est importante, vous devez utiliser un générateur ou list.append dans une boucle for à 2 listes.
Vous ne pouvez pas modifier la variable inplace mais vous pouvez obtenir O(n) avec ceci:
def rearrange(arr):
result = []
for i in arr:
if i < 0:
result.insert(0, i)
else:
result.append(i)
return result
MODIFIER
Suite à la proposition @Chris_Rands, cette solution utilisant deque semble être la plus rapide:
from collections import deque
def rearrange2(arr):
result = deque()
for i in arr:
if i < 0:
result.appendleft(i)
else:
result.append(i)
return result
Environ 28% plus rapidement que la solution acceptée selon les résultats de %timeit.
%timeit rearrange_accepted(nums)
100 loops, best of 3: 12.2 ms per loop
%timeit rearrange2(nums)
100 loops, best of 3: 8.84 ms per loop
Questions connexes
Questions liées
De nouvelles questions
python
Python est un langage de programmation multi-paradigme, typé dynamiquement et polyvalent. Il est conçu pour être rapide à apprendre, comprendre, utiliser et appliquer une syntaxe propre et uniforme. Veuillez noter que Python 2 est officiellement hors support à partir du 01-01-2020. Néanmoins, pour les questions Python spécifiques à la version, ajoutez la balise [python-2.7] ou [python-3.x]. Lorsque vous utilisez une variante Python (par exemple, Jython, PyPy) ou une bibliothèque (par exemple, Pandas et NumPy), veuillez l'inclure dans les balises.