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

示例:

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

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

“`链接:https://leetcode-cn.com/problems/move-zeroes“`

O(n)最后插入0

时间复杂度:O(n)
空间复杂度:O(1)

// Shift non-zero values as far forward as possible
// Fill remaining space with zeros
public void moveZeroes(int[] nums) {
    if (nums == null || nums.length == 0) return;        

    int insertPos = 0;
    for (int num: nums) {
        if (num != 0) nums[insertPos++] = num;
    }        
    while (insertPos < nums.length) {
        nums[insertPos++] = 0;
    }
}

O(n)双指针两次遍历

与上方法类似
时间复杂度:O(n)
空间复杂度:O(1)

class Solution {
    public void moveZeroes(int[] nums) {
        if(nums==null) {
            return;
        }
        //第一次遍历的时候,j指针记录非0的个数,只要是非0的统统都赋给nums[j]
        int j = 0;
        for(int i=0;i<nums.length;++i) {
            if(nums[i]!=0) {
                nums[j++] = nums[i];
            }
        }
        //非0元素统计完了,剩下的都是0了
        //所以第二次遍历把末尾的元素都赋为0即可
        for(int i=j;i<nums.length;++i) {
            nums[i] = 0;
        }
    }
}   

O(n)一次遍历(交换)

时间复杂度:O(n)
空间复杂度:O(1)

class Solution {
    public void moveZeroes(int[] nums) {
        if(nums==null) {
            return;
        }
        //两个指针i和j
        int j = 0;
        for(int i=0;i<nums.length;i++) {
            //当前元素!=0,就把其交换到左边,等于0的交换到右边
            if(nums[i]!=0) {
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j++] = tmp;
            }
        }
    }
}
最后修改日期:2020年10月16日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。