LeetCode 283 Move Zeros 3种解法

这题源自Facebook和Bloomberg。

Move Zero

解法

class Solution {

public:

    void moveZeroes(vector<int>& nums) {

        vector<int> nonZeroElements;

        for(int i=0;i<nums.size();i++)

            if(nums[i])

                nonZeroElements.push_back(nums[i]);

        for(int i=0;i<nonZeroElements.size();i++)

            nums[i]=nonZeroElements[i];

        for(int i=nonZeroElements.size();i<nums.size();i++)

            nums[i]=0;

    }

};

solution

时间复杂度O（n）空间复杂度O（n）。

class Solution {

    public void moveZeroes(int[] nums) {

        int a=nums.length;

        int x=0;

      int[] map=new int[nums.length];

        for(int i=0;i<a;i++)

        {

if(nums[i]!=0)

            {

            map[x]=nums[i];

                x++;

            }

        }

        for(int m=0;m<x;m++)

            nums[m]=map[m];

        for(int i=x;i<nums.length;i++)

            nums[i]=0;

    }

}

java语言版

此问题还可以优化

优化策略在于以上解法使用了辅助空间，使得空间复杂度为O（n），现在可以在原数组上操作。

class Solution {

public:

    void moveZeroes(vector<int>& nums) {

        int k=0;//nums中[0...k)的元素均为非零元素

        //遍历到第i个元素后，保证[0...i]中所有非零元素

        //都按照顺序排列在[0...k)中

        for(int i=0;i<nums.size();i++)

        if(nums[i])

            nums[k++]=nums[i];

        //将nums剩余的位置放置为0

          for(int i=k;i<nums.size();i++)

            nums[i]=0;

    }

};

优化后代码

优化后时间复杂度为O(n)，空间复杂度为O(1)。

接下来的方法则是不改变，设游标k，遍历。如果有非零的则交换位置。k也变为相应的值。

class Solution {

public:

    void moveZeroes(vector<int>& nums) {

        int k=0;//nums中[0...k)的元素均为非零元素

        //遍历到第i个元素后，保证[0...i]中所有非零元素

        //都按照顺序排列在[0...k)中

        //同时，[k...i)为0

        for(int i=0;i<nums.size();i++)

        if(nums[i])

    if(i!=k)

   swap(nums[k++],nums[i]);

  else//i==k

            k++;//避免全是0

    }

};

解法3第10行有一点错误（文中代码已修改）

感想：考虑东西要全面