likes
comments
collection
share

LeetCode.283 移动零

作者站长头像
站长
· 阅读数 8

题目描述:

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

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

示例:

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]

说明:

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

思路分析

双指针法

我们创建两个指针 ilastNoneZeroIndex ,第一次遍历的时候指针 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
            }
        }
    }
}

总结

简单题不配总结。 - -

参考

两种方法轻松团灭 - 移动零 - 力扣(LeetCode) (leetcode-cn.com)

移动零 - 移动零 - 力扣(LeetCode) (leetcode-cn.com)

三种解法 - 移动零 - 力扣(LeetCode) (leetcode-cn.com)

动画演示 283.移动零 - 移动零 - 力扣(LeetCode) (leetcode-cn.com)

转载自:https://juejin.cn/post/6997380552282079240
评论
请登录