283. 移动零

Posted on In , Views: Disqus:
LeetCode刷题系列。

描述

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

示例:

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

说明:

  • 必须在原数组上操作，不能拷贝额外的数组。
  • 尽量减少操作次数。

来源：力扣（LeetCode）
链接：283. Move Zeros

解题思路

根据本题的要求，不允许额外拷贝数组，因此大概率需要进行in-place的操作，同时最后还需要保持非0元素的相对顺序。对于数组元素in-place的操作，比如移动、替换等，可以优先考虑双指针解法，同时配合元素替换函数swap_num，其实现如下：

1
2
3
4
5
6
void swap_num(int *p1, int *p2)
{
    int *tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}

主要的思路如下，设置两个指针：fast和slow，其中fast将会从0遍历整个数组，并找出不为0的元素，并将这些元素与slow索引位置的元素进行交换，且slow指针仅在找到不为0的元素的时候进行移动，可以理解为slow仅仅遍历那些不为0的元素。

这样一趟下来，所有的不为0的元素就都被交换到了数组的前面，最后slow所指向的位置为最后一个不为0的元素，在此之后的元素则都为0。

具体代码可以见解法一。

解法二的思路也类似，也是双指针，只是未借助辅助函数。这样需要在第一遍循环以后，将slow指针后面的元素手动赋值为0。

具体代码可以将解法二。

代码

解法一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//辅助函数
void swap_num(int *p1, int *p2)
{
    int *tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}

void moveZeroes(int* nums, int numsSize)
{
    for(int fast = 0, slow = 0; fast < numsSize; fast++)
    {
        //找到不为0 的元素
        if(*(nums + fast))
        {
            swap_num(nums + fast, nums + slow);
            //慢指针移动
            slow++;
        }
    }
}

解法二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void moveZeroes(int* nums, int numsSize)
{
    int fast = 0, slow = 0;
    
    for(; fast < numsSize; fast++)
    {
        if(nums[fast])
        {
            nums[slow++] = nums[fast];
        }
    }
    
    //将slow指针后面的元素手动赋值为0
    for(int i = slow; i < numsSize; i ++)
    {
        nums[i] = 0;
    }
}