移动零

发表于 更新于
本文字数： 2k 阅读时长 ≈ 2 分钟

LeetCode每日一题，283. MoveZeroes

先看题目描述

DuKy7D.png

大意就是给定一个数组，将其中非零的元素按照顺序放在前面，0 都放在后面

算法和思路

使用双指针，左指针指向当前已经处理好的序列的尾部，右指针指向待处理序列的头部

右指针不断向右移动，每次右指针指向非零数，则将左右指针对应的数交换，同时左指针右移

注意到以下性质：

  • 左指针左边均为非零数

  • 右指针左边直到左指针处均为零

因此每次交换，都是将左指针的零与右指针的非零数交换，且非零数的相对顺序并未改变

个人感觉这个解法有点像快速排序里的 partition 过程

算法源码

双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public void moveZeroes(int[] nums) {
        int len = nums.length;
        int left = 0;
        for (int i = 0; i < len; i++) {
            if (nums[i] != 0) {
                swap(nums, left, i);
                left++;
            }
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

也可以用非零数覆盖前面的 0，最后在末尾补 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public void moveZeroes(int[] nums) {
        int indexNow = 0;
        int indexNum = 0;
        int m = nums.length;

        while(indexNum<m){
            if(nums[indexNum] != 0) {
                nums[indexNow++] = nums[indexNum];
            }
            ++indexNum;
        }

        for(int i = indexNow; i < m; i++){
            nums[i] = 0;
        }
    }
}

下面是自己一开始想的解法，效率比较低

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
class Solution {
    public void moveZeroes(int[] nums) {
        int len = nums.length;
        if (len > 1) {
            int j = 1;
            while (j < len && nums[j] == 0) {
                j++;
            }
            for (int i = 0; i < len; i++) {
                if (nums[i] == 0) {
                    while (j <= i ||  j < len && nums[j] == 0) {
                        j++;
                    }
                    if (j >= len) break;
                    swap(nums, i, j);
                }
            }
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}