Leetcode283. 移动零

2021年5月30日 62Browse 1Like 0Comments

题目描述

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

示例:

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

说明:

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

解题思路

方法一:两层循环

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

参考代码如下:

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(n^2)$

空间复杂度为:$O(1)$

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

方法二:直接覆盖

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

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

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(1)$

agedcat_xuanzai

这个人很懒,什么都没留下

Comments