题目描述

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:
输入: nums = [0]
输出: [0]

题目分析

双指针冒泡

将所有 0 移动到末尾，很容易联想到冒泡排序，但如果先把第一个 0 移动到最后，再来处理下一个 0 ，就需要 2 层循环，时间复杂度 O(n^2)
更好的思路是，使用双指针 left 和 right，left 指向当前第一个0，right 指向当前第一个在 0 后的非 0 数字，让这两个数字互换位置。
left 和 right 初始值都是 0，如果当前数字是 0 则 right 前进一位，如果是非0则 left 和 right 都前进一位。每次发生数字互换后，left 和 right 都前进一位。
时间复杂度 O(n)

原地重写（推荐）

遍历数组，记录非0数字的个数 p，如果当前是非0数字，直接把它放在预期的位置 p-1。全部遍历完之后，再把 >=p 的位置都修改成 0。
时间复杂度 O(n)

Java

public void moveZeroes1(int[] nums) {
    int left = 0;
    int right = 0;
    while (right < nums.length) {
        if (nums[right] != 0) {
            if (left != right) {
                int t = nums[left];
                nums[left] = nums[right];
                nums[right] = t;
            }
            left++;
        }
        right++;
    }
}

public void moveZeroes2(int[] nums) {
    int p = 0; // 非0数字总数
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] != 0) {
            p++;
            nums[p - 1] = nums[i];
        }
    }
    for (int i = p; i < nums.length; i++) {
        nums[i] = 0;
    }
}

Kotlin

fun moveZeroes1(nums: IntArray) {
    var left = 0
    var right = 0
    while (right < nums.size) {
        if (nums[right] != 0) {
            if (left != right) {
                val t = nums[left]
                nums[left] = nums[right]
                nums[right] = t
            }
            left++
        }
        right++
    }
}

fun moveZeroes2(nums: IntArray) {
    var p = 0 // 非0数字总数
    for (i in nums.indices) {
        if (nums[i] != 0) {
            p++
            nums[p - 1] = nums[i]
        }
    }
    for (i in p until nums.size) {
        nums[i] = 0
    }
}