题目#

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

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

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

5
示例 2:
6
输入: nums = [0]
7
输出: [0]

我的算法#

1
void moveZeroes(int* nums, int numsSize) {
2
for (int i=0;i<numsSize;i++)
3
    {
4
        int j=i;
5
        for(;j>=0;j--)
6
        {
7
            if(nums[j]==0)
8
            {
9
                int temp=nums[j];
10
                nums[j]=nums[i];
11
                nums[i]=temp;
12
            }
13
        }
14
    }
15
}

解题思路

1. 一开始我看到这道题的时候其实已经想到了通过后面非0数与前面的0交换的方式来实现题目要求.实际操作起来的时候我也就是按照这个想法写的:即通过遍历当前数前面的数,找出全部的0并与它们一一交换让前面的0不断移到数组后面去.

踩过的坑

1. 脑子抽了,nums[j]==0 写成了 nums[j]=='0' 导致一开始一直输出 48.

用双指针的算法#

1
void moveZeroes(int* nums, int numsSize) {
2
    int slow=0;
3
    for(int fast=0;fast<numsSize;fast++)
4
    {
5
        if(nums[fast]!=0)
6
        {
7
            int temp=nums[fast];
8
            nums[fast]=nums[slow];
9
            nums[slow]=temp;
10
            slow++;
11
        }
12
    }
13
}

解题思路

1. 其实我之前的思路已经和答案非常接近了,不过答案采取的是更高效的方法.它只需要一次遍历就可以,而我之前的算法每个元素都需要遍历该元素前面的所有元素,所以时间复杂度只有 O(n).
2. 答案的思路大致如下:先初始化一快一慢两个指针:快指针遍历数组,用来寻找非0的数;而慢指针则用来按顺序指向新数组(实际上并不是新的数组,而只是原数组经过在自身上操作重排后得到的数组)的下标. 快指针找到非0的数之后就与慢指针所指向的内存中存的数交换,这样就可以把0不断地移到最后.
3. 需要注意的是:如果快指针与慢指针同时指向一块存着非0数的内存是没有影响的(比如 int c={1,0,2,4,0,3} 这个数组一开始快指针与慢指针都指向c[0]).为什么呢?因为此时该数会自己与自己交换(其实也就等价与没有交换),交换后两个指针都会同时向后移.在这个例子中,向后移之后就到了 c[1]=0 ,那么此时慢指针就会停下来,快指针会继续往前找非0的数,那么就可以正常通过交换来实现 把0向后移的操作 了.

附一张运行结果的截图(第一次看到还能击败100%的人🤣)