539.移动零

描述

给一个数组 nums 写一个函数将 0 移动到数组的最后面，非零元素保持原数组的顺序

注意事项

1.必须在原数组上操作
2.最小化操作数

样例

给出 nums = [0, 1, 0, 3, 12], 调用函数之后, nums = [1, 3, 12, 0, 0].

知识点

相向，同向型两根指针一直往前走，时间复杂度都为 O(n)，若左指针前进一步右指针回到初始位置重新走的话时间复杂度为 O(n^2),两根指针一般用在 O(n) 的时间复杂度，要比 O(nlogn) 快

思路

用同向型指针，一个指向第一个为 0 的元素，一个指向第一个不为 0 的元素，在向右移动过程中不断把 0 交换到数组的末尾

代码

统计数组中 0 的个数，把不为 0 的数按照顺序全部加入到动态数组中，然后在按照统计个数把 0 加入，最后用数组复制下动态数组中的元素，时间复杂度 O(n) 空间复杂度 O(n)

public class Solution {
    /*
     * @param nums: an integer array
     * @return: 
     */
    public void moveZeroes(int[] nums) {
        int count = 0;
        ArrayList<Integer> array = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                array.add(nums[i]);
            } else {
                count++;
            }
        }
        
        while (count-- != 0) {
            array.add(0);
        }
        
        for (int i = 0; i < nums.length; i++) {
            nums[i] = array.get(i);
        }
    }
}

遍历过程中直接把非 0 数全拷贝到 nums 数组中，后面空位全部补 0，时间复杂度 O(N)，空间复杂度 O(1)
不存在非 0 数被覆盖的情形，0 被覆盖，非 0 数停留在原地

public class Solution {
    /*
     * @param nums: an integer array
     * @return: 
     */
    public void moveZeroes(int[] nums) {
        int lastNoZeroIndex = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                nums[lastNoZeroIndex++] = nums[i];
            }
        }
        
        for (int i = lastNoZeroIndex; i < nums.length; i++) {
            nums[i] = 0;
        }
    }
}

上一种的时间复杂度在遍历完一遍数组后又遍历了 0 的个数，用两根指针优化时间复杂度，让算法只遍历一遍数组，时间复杂度 O(N)，空间复杂度 O(1)
AAA000BC ————> AAAB000C
left 始终指向第一个0只是下标在移动，right 刚开始指向 B，交换完后后移一位指向 C，始终是指向第一个非 0 数

public class Solution {
    /*
     * @param nums: an integer array
     * @return: 
     */
    public void moveZeroes(int[] nums) {
        // left 代表数组中第一个值为 0 的下标
        // right 代表数组中第一个值不为 0 的下标
        int left = 0, right;
        for (right = 0; right < nums.length; right++) {
            if (nums[right] != 0) {
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                /* 在没遇到第一个 0 之前，right 每移动一次 left 也跟着移动，
                 * left 和 right 始终指向同一元素，交换也是自己和自己的交换，
                 * 所以不会出现如果数组第一个元素不是 0，right++跑到 0，
                 * 而 left 仍在数组第一个元素处不动的反向交换情形
                 */
                left++;
            }
        }
    }
}

539.移动零

代码

推荐阅读更多精彩内容