题目描述(简单难度)

将所有的 0 移动到末尾,并且保持其他数字的相对顺序不变。

解法一

我的第一反应是利用两个指针,一个指针指向开头,一个指针指向末尾非零元素,然后从开头指针遍历,如果遇到 0 就和末尾指向的元素相交换,末尾指针向前移动到非零元素。

这就保证末尾指针后边元素全部是 0,当首尾指针相遇的时候结束。

但是上边的想法会使得其他数字的相对顺序改变了,我们可以逆转一下思路。不是将 0 放到末尾,而是将所有非零元素放到开头,这样就保证末尾剩下的都是 0 了。

同样利用双指针,指针 i 用于遍历数组,指针 j 开始指向开头,保证它前边的所有元素都是非 0 元素。

i 指针遇到非零元素就和 j 指针指向的元素交换,j 指针然后后移。

0,1,0,3,12 为例模拟一下过程。

0,1,0,3,12
^
i
j

nums[i] == 0, i 后移
0,1,0,3,12
^ ^
j i

nums[i] != 0, 交换和 j 指向的元素, i 后移, j 后移
1,0,0,3,12
  ^ ^
  j i

nums[i] == 0, i 后移
1,0,0,3,12
  ^   ^
  j   i

nums[i] != 0, 交换和 j 指向的元素, i 后移, j 后移
1,3,0,0,12
    ^   ^
    j   i

nums[i] != 0, 交换和 j 指向的元素, i 后移, j 后移, 遍历结束
1,3,12,0,0
       ^   ^
       j   i

可以注意到 j 前边的元素始终都是非零元素,可以结合代码再看下。

public void moveZeroes(int[] nums) {
    int j = 0;
    for (int i = 0; i < nums.length; i++) {
        //不等于 0 就交换
        if (nums[i] != 0) {
            int temp = nums[j];
            nums[j] = nums[i];
            nums[i] = temp;
            j++;
        }
    }
}

比较简单的一道题,双指针经常用到。用一个指针用来分割元素,使得它前边都是符合某种条件的元素。在快速排序中,也有用到这个思想。

results matching ""

    No results matching ""