LeetCode.283 移动零-一一网

这是我参与8月更文挑战的第17天，活动详情查看：8月更文挑战

题目描述：

283. 移动零 – 力扣（LeetCode） (leetcode-cn.com)

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

示例:

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
复制代码

说明:

必须在原数组上操作，不能拷贝额外的数组。
尽量减少操作次数。

思路分析

双指针法

我们创建两个指针 i 和 lastNoneZeroIndex ，第一次遍历的时候指针 lastNoneZeroIndex 用来记录当前有多少非0元素。即遍历的时候每遇到一个非0元素就将其往数组左边挪，第一次遍历完后，lastNoneZeroIndex 指针的下标就指向了最后一个非0元素下标。

第二次遍历的时候，起始位置就从 lastNoneZeroIndex 开始到结束，将剩下的这段区域内的元素全部置为0。

AC代码

class Solution {
    fun moveZeroes(nums: IntArray): Unit {
        var lastNoneZeroIndex = 0;

        for ( i in 0..nums.lastIndex) {
            if (nums[i] != 0) {
                nums[lastNoneZeroIndex++] = nums[i];
            }
        }

        for ( m in lastNoneZeroIndex.. nums.lastIndex) {
            nums[m] = 0;
        }
    }
}

复制代码

上述代码我们使用了两层循环，题目要求我们尽量减少操作次数，我们现在优化为一层循环的写法。

class Solution {
    fun moveZeroes(nums: IntArray): Unit {
        var lastNoneZeroIndex = 0;

        for (i in 0..nums.lastIndex) {
            if (nums[i] != 0) {
                var temp = nums[i]
                nums[i] = nums[lastNoneZeroIndex]
                nums[lastNoneZeroIndex++] = temp
            }
        }
    }
}
复制代码

利用kotlin的语法特性，我们还能写出更优雅的代码

class Solution {
    fun moveZeroes(nums: IntArray): Unit {
        var index = 0
        for ((i, value) in nums.withIndex()) {
            if (value != 0) {
                nums[i] = nums[index]
                nums[index++] = value
            }
        }
    }
}
复制代码