乐趣区

LeetCode-283移动零-Move-Zeroes

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

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.

示例:

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

说明:

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

Note:

  1. You must do this in-place without making a copy of the array.
  2. Minimize the total number of operations.

解题思路:

​ 千万不要被题目局限了思维!题目让把所有 0 移到末尾,如果你的思路是遇零与末尾数字交换位置,然后还需要把非零数字排序,那么就被带偏了。

​ 换个思路,把 非 0 数字前移,不去管数字 0

定义两个指针:指针 i 直接遍历数组遇到非 0 数字把该数字赋值给指针 j 所在的索引,索引 j 自增 1,i 继续遍历。

这样遍历完之后,数组索引从 0 到 j 之间的数值即为所求得 保持非零元素的相对顺序,而 j 之后的数值只需要全部赋值 0 即可。

Java:

class Solution {public void moveZeroes(int[] nums) {
        int numsLen = nums.length;
        if (numsLen < 1) return;// 数组长度小于一直接返回
        int j = 0;
        for (int i = 0; i < numsLen; i++) {// 遍历数组
            if (nums[i] != 0) {// 如果该数不为 0
                nums[j++] = nums[i];// 赋值给索引 j
            }
        }
        while (j < numsLen) nums[j++] = 0;// 把从 j 到末尾所有数字赋值 0
    }
}

Python3:

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """Do not return anything, modify nums in-place instead."""
        if len(nums) < 1:
            return
        j = 0
        for num in nums:
            if num != 0:
                nums[j] = num
                j += 1
        for i in range(j, len(nums)):
            nums[i] = 0

如果题目不限制在原数组上操作,用 python 一行可解决:

nums = [i *for* i in nums *if* i != 0]+[i *for* i in nums *if* i == 0]

公众号: 爱写 bug(ID:iCodeBugs)

退出移动版