From c8330adfcb2bf86c4ad35091d805f35603bc55e0 Mon Sep 17 00:00:00 2001 From: William Carroll Date: Sun, 15 Nov 2020 13:51:46 +0000 Subject: Solve "Move Zeroes to End" Write a function to modify an array of integers in-place such that all of the zeroes in the array are at the end, and the order of the other integers is not changed. --- scratch/facebook/move-zeroes-to-end.py | 26 ++++++++++++++++++++++++++ 1 file changed, 26 insertions(+) create mode 100644 scratch/facebook/move-zeroes-to-end.py diff --git a/scratch/facebook/move-zeroes-to-end.py b/scratch/facebook/move-zeroes-to-end.py new file mode 100644 index 000000000000..aa9f73d6f11d --- /dev/null +++ b/scratch/facebook/move-zeroes-to-end.py @@ -0,0 +1,26 @@ +def move_zeroes_to_end(xs): + n_zeroes = 0 + for x in xs: + if x == 0: + n_zeroes += 1 + + i = 0 + while i < len(xs) - 1: + if xs[i] == 0: + j = i + 1 + while j < len(xs) and xs[j] == 0: + j += 1 + if j >= len(xs): + break + xs[i], xs[j] = xs[j], xs[i] + i += 1 + # add zeroes to the end + for i in range(n_zeroes): + xs[len(xs) - 1 - i] = 0 + +xs = [1, 2, 0, 3, 4, 0, 0, 5, 0] +print(xs) +move_zeroes_to_end(xs) +assert xs == [1, 2, 3, 4, 5, 0, 0, 0, 0] +print(xs) +print("Success!") -- cgit 1.4.1