283. Move Zeroes

题目描述和难度

  • 题目描述:

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

示例:

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

说明:

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

思路分析

求解关键:这道题的写法有 2 种,一种是没有学习过算法都很容易想到的,另一种其实只要算法基础扎实,也是非常容易想到的。

  • 思路1:遍历一遍数组,把非零值覆盖在数组的前面,最后在把数组的末尾全部赋值为 0。

这个思路比较容易想到,但是只要熟悉了快速排序,应该更容易想到下面的写法。

  • 思路2(推荐):借助快速排序 partition 的思想,遇到 0 就放过,遇到非 0 ,这是符合题目中“尽量减少操作次数”这个要求的。

就逐个交换到数组的前面。更推荐使用这种写法,简洁。

在练习的时候,我还想到了“指针对撞”的思路,可以使得非零元素排在零元素前面,但是不能做到“保持非零元素的相对顺序”。

参考解答

参考解答1

Java 写法:

public class Solution {

    public void moveZeroes(int[] nums) {
        // 遍历指针
        int i = 0;
        // 一开始都写非零元素,然后都写零元素
        int j = 0;
        for (; i < nums.length; i++) {
            if (nums[i] != 0) {
                nums[j++] = nums[i];
            }
        }

        for (int k = j; k < nums.length; k++) {
            nums[k] = 0;
        }
    }
}

Python 写法:

class Solution:
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """

        not_zero_begin = 0

        for i in range(len(nums)):
            if nums[i] != 0:
                nums[not_zero_begin] = nums[i]
                not_zero_begin += 1

        for i in range(not_zero_begin, len(nums)):
            nums[not_zero_begin] = 0
            not_zero_begin += 1

参考解答2

Java 写法:

public class Solution3 {

    // https://leetcode-cn.com/problems/move-zeroes/description/
    // [0, 1, 0, 3, 12]
    // [1, 0, 0, 3, 12]
    // [1, 3, 0, 0, 12]
    // [1, 3, 12, 0, 0]
    // 常规题:用思维定势就可以完成
    /**
     * i 用于遍历
     * 在区间 [0,j) 里,所有的值都非零
     * 而在区间 [j,i) 里,所有的值都为零
     * 初始化的时候 j = 0 , i = 0
     *
     * @param nums
     */
    public void moveZeroes(int[] nums) {
        int j = 0;
        for (int i = 0; i < nums.length; i++) {
            if(nums[i]!=0){
                swap(nums,i,j);
                j++;
            }

        }
    }

    private void swap(int[] nums,int index1,int index2){
        if(index1==index2){
            return;
        }
        int temp = nums[index1];
        nums[index1] =nums[index2];
        nums[index2] = temp;
    }
}

Python 写法:

class Solution:

    # 快速排序的方法,最简单,最直接

    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """

        # [0,not_zero_end) 保持都非 0,
        # [not_zero_end,len-1] 为 0
        not_zero_end = 0

        for i in range(len(nums)):
            if nums[i] != 0:
                self.__swap(nums, not_zero_end, i)
                not_zero_end += 1

    def __swap(self, nums, index1, index2):
        if index1 == index2:
            return
        temp = nums[index1]
        nums[index1] = nums[index2]
        nums[index2] = temp

Python 写法:

class Solution:

    # 快排实现:
    # Python 交换数组中的元素,可以用 Python 特殊的语法实现

    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """

        not_zero_end = 0  # 不包括末尾元素
        for j in range(len(nums)):
            if nums[j] != 0:
                nums[not_zero_end], nums[j] = nums[j], nums[not_zero_end]
                not_zero_end += 1

本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0283-move-zeroes ,如果我的题解有错误,或者您有更好的解法,欢迎您告诉我 liweiwei1419@gmail.com