【每日一题】Leetcode - 283. 移动零-Toy模板网

这篇具有很好参考价值的文章主要介绍了【每日一题】Leetcode - 283. 移动零。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目

Leetcode - 283. 移动零

解题思路

从右向左遍历，遇到0，就将后面所有元素前移，同时更新长度，使其减1，因为移动n次，倒数n位就被0占据，后续操作可忽略

class Solution {
    public void moveZeroes(int[] nums) {
        if (nums.length == 1) {
            return;
        }
        int length = nums.length;
        for (int i = length - 1 - 1; i >= 0; i--) {
            if (nums[i] == 0) {
                for (int j = i + 1; j < length; j++) {
                    nums[j - 1] = nums[j];
                }
                nums[length - 1] = 0;
                length--;
            }
        }
    }
}

【每日一题】Leetcode - 283. 移动零

优化

前面的操作，从右向左，每次遇到0移动都要跑半个数组，慢在整体前移；
换个思路，从左向右，记录首个0的位置，将后面的第一个非0元素和它替换，然后依次这样操作，前移优化成了O(1)

class Solution {
    public void moveZeroes(int[] nums) {
        if (nums.length == 1) {
            return;
        }

        //  find first the zero number of position
        int left = 0;
        while (left < nums.length) {
            if (nums[left] == 0) {
                break;
            }
            left++;
        }
        int right = left + 1;
        while (left < nums.length && right < nums.length) {
            if (nums[right] == 0) {
                right++;
                continue;
            }
            nums[left++] = nums[right];
            nums[right++] = 0; // ensure the left + 1 position is always a zero number position
        }
    }
}