283. Move Zeroes - Easy

前往題目

想法

• 只想得到用一個額外的陣列儲存非零項，這樣空間和時間都是O(N)

思路

題目很詐，說move all 0's to the end of it，這樣第一眼就在想要怎麼把0移到後面，但其實只要反過來想，把非零項移到前面就好了，最後再補上零即可…

1. 把非零項移到前面
2. 補上所需的零

Code

class Solution {
    public void moveZeroes(int[] nums) {
        int index = 0;

        // Move non-zero elements to the front
        for (int num : nums) {
            if (num != 0) {
                nums[index] = num;
                ++index;
            }
        }

        // Add all the zeros
        while (index < nums.length) {
            nums[index] = 0;
            ++index;
        }

        return;
    }
}

2024/07/10

• 嘗試把0和非0數字往前移，雖然交換成功但是順序被打亂，不是題目所要的

▶

WA

class Solution {
    public void moveZeroes(int[] nums) {
        int l = 0, r = nums.length - 1;

        while (l < r) {
            if (nums[l] == 0) {
                // Avoid right pointer on zero
                while (l < r && nums[r] == 0) {
                    --r;
                }
                // Swap
                nums[l] = nums[r];
                nums[r] = 0;
            }
            ++l;
        }
        return;
    }
}