Cyclic Sort
Étant donné une liste contenant n objets. Chaque objet s'est vu attribuer un numéro unique de 1 à n lors de sa création, en fonction de l'ordre dans lequel il a été créé.
Créez une fonction qui trie les objets sur place en fonction de nombres consécutifs de O (n). Aucune structure de données supplémentaire n'est nécessaire. Par souci de simplicité, supposons que vous receviez une liste d'entiers contenant uniquement des nombres consécutifs. Cependant, chaque numéro est en fait un objet.
Input: [3, 1, 5, 4, 2] Output: [1, 2, 3, 4, 5]
Input: [2, 6, 4, 3, 1, 5] Output: [1, 2, 3, 4, 5, 6]
Input: [1, 5, 6, 4, 3, 2] Output: [1, 2, 3, 4, 5, 6]
Solution Comme vous le savez, la liste contient des nombres compris entre 1 et n. Profitez de ce fait pour trouver un moyen efficace de trier les nombres. Tous les numéros sont uniques, vous pouvez donc placer chaque numéro dans la bonne position. Autrement dit, 1 est placé à l'index 0, 2 est placé à l'index 1, et ainsi de suite.
Pour placer un nombre (ou un objet en général) dans l'index correct, vous devez d'abord le trouver. Si vous trouvez d'abord le numéro et le mettez au bon endroit, O (N ^ 2), c'est inacceptable.
Au lieu de cela, répétez la liste avec un nombre à la fois, et si le numéro actuel n'est pas dans l'index correct, remplacez-le par le nombre dans l'index correct. De cette façon, il recherche tous les nombres, les met dans le bon index et trie la liste entière.
def cyclic_sort(nums):
i = 0
while i < len(nums):
j = nums[i] - 1
if nums[i] != nums[j]:
nums[i], nums[j] = nums[j], nums[i] # swap
else:
i += 1
return nums
def main():
print(cyclic_sort([3, 1, 5, 4, 2]))
print(cyclic_sort([2, 6, 4, 3, 1, 5]))
print(cyclic_sort([1, 5, 6, 4, 3, 2]))
main()
Recommended Posts