leetcode系列：移动零

Posted on | In , | 次阅读

描述

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.

思路

解一

设置两个指针i、j，用i指向为0的数字，用j指向不为0的数字。只有当j>i的时候，才需要交换nums[i],nums[j]。那么先遍历一遍数组，用i来表示，如果nums[i]不为0，跳过；如果为0，才有可能交换。然后将i赋值给j，找到i之后的为0的下标，交换nums[i],nums[j]。注意i、j不能越界。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void moveZeroes1(int[] nums) {
    int j = 0;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == 0) {
            j = i;
            while (j < nums.length && nums[j] == 0) {
                j++;
            }
            if (j < nums.length) {
                swap(nums, i, j);
            }
        }
    }
}

该算法的时间复杂度不理想，最坏情况下是 O（N^2）

解二

参考冒泡的思想，两个之间逐个比较，如果有前面的那个为0，就交换位置。利用其稳定性，可以保证不为0元素的顺序。

1
2
3
4
5
6
7
8
9
public static void moveZeroes2(int[] nums) {
    for (int i = 0; i < nums.length - 1; i++) {
        for (int j = 0; j < nums.length - i - 1; j++) {
            if (nums[j] == 0) {
                swap(nums, j, j + 1);
            }
        }
    }
}

按照冒泡思想可以优化，优化后的最好时间复杂度为O（N），最坏还是 O（N^2）

解三

对解一的优化，避免多余的比较和查找。利用双指针的优势，将时间复杂度压缩到O（N），思路如下：

设置两个指针i、j，用i指向不为0的数字，用j指向为0的数字。只有当i>j的时候，才需要交换nums[i],nums[j]。i、j分别从0开始，如果nums[i]==0,i++；如果nums[j]!=0,j++；如果i>j并且nums[i] != 0，交换i,j的值，并且同时加一，否则i++;注意边界不超过len。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static void moveZeroes3(int[] nums) {
    int i = 0;
    int j = 0;
    while (i < nums.length && j < nums.length) {
        if (nums[i] == 0) {
            i++;
        }
        if (nums[j] != 0) {
            j++;
        }

        if (i > j && i < nums.length && nums[i] != 0) {
            swap(nums, i++, j++);
        } else {
            i++;
        }
    }
}

该程序注意死循环问题，为了避免死循环，才需要i++。该程序最坏要走2N部，时间复杂度为O(n)。另外我们swap也能进行优化，因为我们知道nums[j] = 0

nums[j] = nums[i];
nums[i] = 0;

参考

参一

统计出不为0的个数，将不为0的赋值给数组前几位，后续的用0补充

1
2
3
4
5
6
7
8
9
10
11
12
13
// 参考
public static void moveZeroes4(int[] nums) {
    int tmp = 0;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] != 0) {
            nums[tmp++] = nums[i];
        }
    }

    for (int i = tmp; i < nums.length; i++) {
        nums[i] = 0;
    }
}

时间复杂度O（N）

参二

快慢指针思想，j是慢指针，指向为0的元素，i是快指针为不为0元素。快指针将所有不为0的元素，赋值给前面为0的元素，直到全为0。

1
2
3
4
5
6
7
8
9
10
11
12
public static void moveZeroes5(int[] nums) {
    int j = 0;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] != 0) {
            nums[j] = nums[i];
            if (i != j) {
                nums[i] = 0;
            }
            j++;
        }
    }
}

时间复杂度O（N）

github

代码地址对应的是提交记录，方便参看当时踩过的坑。