当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.283.Move Zeroes 将数组中的零移到末尾

LeetCode.283.Move Zeroes 将数组中的零移到末尾

题目描述

283 Move Zeroes
https://leetcode-cn.com/problems/move-zeroes/
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.

Example:

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

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


解题过程

相似题目
LeetCode.283.Move Zeroes 将数组中的零移到末尾
LeetCode.027.Remove Element 从数组中移除指定元素
LeetCode.026.Remove Duplicates from Sorted Array 删除有序数组中的重复项
LeetCode.080.Remove Duplicates from Sorted Array II 删除有序数组中的重复项2

SolutionV2018

读完题意就想到用交换,类似冒泡排序,把0逐渐都换到后面去,把非0换到前面,写了一版通过了,但非常慢,只打败了1.3%的代码:

class Solution {
    public void moveZeroes(int[] nums) {
        boolean swaped=true;//上次循环是否有过交换
        for(int i=1; i<nums.length && swaped; i++){
            swaped = false;
            for(int j=0; j<nums.length-i; j++){
                if(nums[j]==0 && nums[j+1]!=0){//交换
                    swaped=true;
                    nums[j] = nums[j] ^ nums[j+1];
                    nums[j+1] = nums[j] ^ nums[j+1];
                    nums[j] = nums[j] ^ nums[j+1];
                }
            }
        }
    }
}

基本上就是冒泡排序的套路,O(n^2)复杂度,很慢。

然后看Solution,给出了3个逐渐优化的方法:
第一种方法是不用任何技巧,新申请一个等长数组,先把非零元素逐个放进去,再把后面都补上0,最后赋值给原数组。当然这个方法不符合题中原地操作(in-place)的要求。
第二种方法,双指针,从前往后遍历数组,用慢指针k表示第k+1个非零元素的最终位置,由于所有非零元素肯定最终都排在数组前面,所以只要遍历到一个非零元素就可以放到nums[k]中。最后把剩下的(nums.length-k)个元素赋值为0即可。O(n)复杂度,很不错的方法了。

class Solution {
    public void moveZeroes(int[] nums) {
        if(nums.length < 2) return;
        int k = 0;
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] != 0) {
                nums[k++] = nums[i];
            }
        }
        for(;k < nums.length; k++)
            nums[k] = 0;
    }
}

对第二种方法,有一个优化,就是在一趟遍历过程中就将剩下的位置设为0,不需要最后再单独来一遍。里面的思想是,当右指针大于左指针时,说明右指针和左指针之间有0,这时候才需要把非零值换到前面,同时,把右指针位置设为0,省的最后再来一遍:

public void moveZeroes(int[] nums) {
    int leftMostZeroIndex = 0; // The index of the leftmost zero
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] != 0) {
            if (i > leftMostZeroIndex) { // There are zero(s) on the left side of the current non-zero number, swap!
                nums[leftMostZeroIndex] = nums[i];
                nums[i] = 0;
            }

            leftMostZeroIndex++;
        }
    }
}

第三种方法,还是第二种方法的优化,但比较难懂,每次遍历到非零值时,左右指针的值交换。想要弄明白为什么交换,得分开分析:
1、left==right时,表明right左边没有0值出现,其实这时没必要交换,当然做一下交换也不会出错。
2、left<right时,说明右指针right左边出现了0值,此时0值肯定在left位置,即nums[left]==0,所以这个left,right交换动作其实相当于nums[left]=nums[right]; nums[right]=0;
所以这个第三种方法和上面的第二种方法的优化是一样的,只是写法不同,写成swap让人比较难懂,而且还少了left==right时不需交换的优化。

class Solution {
    public void moveZeroes2(int[] nums) {
        for(int left = 0,right=0; right < nums.length; right++)
            if (nums[right] != 0){
                int temp = nums[right];
                nums[right] = nums[left];
                nums[left] = temp;
                left++;
            }
    }
}

SolutionV2020

private static  class SolutionV2020 {
    public void moveZeroes(int[] nums) {
        if (null == nums || nums.length < 2) {
            return;
        }
        // left左边是要保留的非零元素
        int left = 0;
        for (int right = 0; right < nums.length; right++) {
            if (nums[right] != 0) {
                if (right != left) {
                    nums[left] = nums[right];
                }
                left++;
            }
        }
        // left右边的元素置为0
        while (left < nums.length) {
            nums[left++] = 0;
        }
    }
}

GitHub代码

algorithms/leetcode/leetcode/_283_MoveZeroes.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_283_MoveZeroes.java


上一篇 LeetCode.007.Reverse Integer

下一篇 LeetCode.541.Reverse String II 反转字符串 II

阅读
评论
1k
阅读预计4分钟
创建日期 2018-01-27
修改日期 2020-02-19
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论