[LeetCode] 283. Move Zeroes（移动零）

• Difficulty: Easy

• Related Topics: Array, Two Pointers

• Link: https://leetcode.com/problems/move-zeroes/

Description

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

给定一个数组 num，写一个函数把该数组里的 0 全部移动到数组的末尾。同时保持非零元素的相对位置。

Examples

Input: [0,1,0,3,12]
Output: [1,3,12,0,0]

Note

1. You must do this in-place without making a copy of the array.

   你必须原地修改该数组（不能复制该数组）

2. Minimize the total number of operations.

   操作次数越少越好

Hint

1. In-place means we should not be allocating any space for extra array. But we are allowed to modify the existing array. However, as a first step, try coming up with a solution that makes use of additional space. For this problem as well, first apply the idea discussed using an additional array and the in-place solution will pop up eventually.

   原地修改意味着我们不能使用额外的数组空间，但可以修改译由的数组。不过作为第一步，可以先尝试着在使用额外空间的情况下解答本题。在这题里，就是制作一份数组的拷贝来解答该问题，然后原地修改的方法就水落石出了。

2. A two-pointer approach could be helpful here. The idea would be to have one pointer for iterating the array and another pointer that just works on the non-zero elements of the array.

   双指针法在这题里应该有用。思路是用一个指针遍历整个数组，用另一个指针遍历数组中的非零元素。

Solution

参照 Hint 里的做法（双指针），具体代码如下

class Solution {
    fun moveZeroes(nums: IntArray) {
        // 找到第一个零的位置，如果没找到就直接返回
        val zeroIndex = nums.indexOfFirst { it == 0 }
        if (zeroIndex == -1) {
            return
        }
        // 双指针，一个指针表示非零元素的目标地址，另一个表示非零元素的初始位置
        var i = zeroIndex
        var j = zeroIndex
        while (true) {
            j++
            while (j < nums.size && nums[j] == 0) {
                j++
            }
            if (j >= nums.size) {
                break
            }
            // 将非零元素不断从后面往前面填充
            nums[i] = nums[j]
            i++
        }

        // 遍历到最后，i 之后的空间填 0 即可
        while (i < nums.size) {
            nums[i++] = 0
        }
    }
}