Leetcode-283-移动0

Leecode-283-移动零

题目描述

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

示例:

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

说明:

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

方法一：两次遍历

• 创建两个指针 i 和 j
• 第一次遍历指针 j 记录 当前有多少非0的元素，即遍历的时候每遇到一个非0的元素就将它向左边挪
• 第一次遍历完之后，j 指针就记录了最后一个非0元素的下标。
• 第二次遍历的时候，起始位置从 j 开始到结束，把所有剩下的元素都修改为0。

// 两次遍历
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];
                j++;
            }
        }

        // 第二次遍历把末尾的元素全部赋值为0
        // 非0元素统计完了，剩下的都是0了
        for (int i = j;i < nums.length; i++){
            nums[i] = 0;
        }
    }
}


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

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

方法二：一次遍历

• 参考快速排序的思想
  • 首先确定一个带分割的点 x ，
  • 然后把所有小于等于x 的都放到 x的左边，把所有大于 x 的都放到 x的右边
  • 这里的 x 根据题目 取 0 . (把所有小于等于0的都放在0的左边，所有大于0的都放在0的右边)

• 这的中间点就是0本身，所以实现起来比快速排序简单很多，我们使用两个指针i和j，只要nums[i]!=0，我们就交换nums[i]和nums[j]

class Solution {
    public void moveZeroes(int[] nums) {
        if (nums == null){
            return;
        }

        // 双指针交换
        int j = 0;
        for (int i = 0; i < nums.length; i++) {
            // 当前元素不等于0.就把它交换到左边
            // 等于0就交换到右边
            if (nums[i] != 0){
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
                j++;
            }
        }
    }
}

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

打赏