LeetCode 283、移动零

LeetCode 283、移动零

描述

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

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

1
2
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:

1
2
输入: nums = [0]
输出: [0]

提示:

  • 1 <= nums.length <= 104
  • -231 <= nums[i] <= 231 - 1

进阶：你能尽量减少完成的操作次数吗？

思路

思路一：冒泡排序

以此比较遇到零就后移

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/*
 * @lc app=leetcode.cn id=283 lang=java
 *
 * [283] 移动零
 */

// @lc code=start
class Solution {
    public void moveZeroes(int[] nums) {
        for (int i=0;i<nums.length;i++){
            if (nums[i]==0){
                for (int j=i+1;j<nums.length;j++){
                    if (nums[j]!=0){
                        int temp=nums[i];
                        nums[i]=nums[j];
                        nums[j]=temp;
                        break;
                    }
                }
            }
       }
    }
}
// @lc code=end

思路二

看下列注释

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// 移动零（LeetCode 283）：https://leetcode.cn/problems/move-zeroes/
class Solution {
    public void moveZeroes(int[] nums) {

        // 设置一个变量，用来指向经过一系列操作后数组中所有为 0 元素的第一个位置上
        // 一开始默认在索引为 0 的位置
        int slow = 0;

        // 从头到尾遍历数组
        // 遍历完毕之后，slow 指向了一个为 0 的元素，或者如果数组中不存在 0 ，就和 fast 一样，超过了数组的范围
        for (int fast = 0; fast < nums.length; fast++) {

            // 在遍历过程中，如果发现访问的元素是非 0 元素
            // 说明 slow 不在正确的位置上，需要向后移动，寻找合适的位置
            if (nums[fast] != 0) {

                // 这个时候，原先 slow 的值需要被 fast 的值覆盖
                nums[slow] = nums[fast];

                // slow 需要向后移动，寻找合适的位置
                slow++;

            }
        }

        // 接下来，只需要把 slow 极其后面所有的元素都设置为 0 就行
        for (int i = slow; i < nums.length; i++) {

            // 都设置为 0 
            nums[i] = 0;

        }
    }
}