Leetcode283. 移动零

题目描述

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

示例:

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

说明:

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

解题思路

方法一：两层循环

刚开始我想复杂了，首先逐个遍历整个数组，如果碰到0，那么就在这个元素后面找一个非0的进行交换，如果找不到非0的，说明已经完成了。

参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void moveZeroes(vector<int>& nums)
{
    for(int i=0;i<nums.size();++i)
    {
        if(nums[i]!=0) continue;
        int j=i+1;
        for(;j<nums.size();++j)
        {
            if(nums[j]==0) continue;
            swap(nums[i],nums[j]);
            break;
        }
        if(j==nums.size()) break;
    }
}

时间复杂度为：O(n2)O(n^2)

空间复杂度为：O(1)O(1)

这个方法效率有点低，只击败了9%。。。

方法二：直接覆盖

这个方法的思想很简单，遍历整个数组，将数组中的非0元素直接映射到数组的前面，后面部分直接改为0就可以了。变量index记录了遍历过的部分有多少个非零元素，以及出现新的非0元素应该填入数组位置的下标。

具体细节如下述代码所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void moveZeroes(vector<int>& nums)
{
    int len=nums.size();
    int index=0;
    for(auto num : nums)
    {
        if(num!=0)
        {
            nums[index++]=num;
        }
    }
    for(int i=index;i<len;++i)
    {
        nums[i]=0;
    }
}

时间复杂度为：O(n)O(n)

空间复杂度为：O(1)O(1)