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