leetcode 283 移动零

第一反应只会写冒泡的,但是注意要从后往前冒泡,每遇到一个0就一直向后交换,直到最后,不然遍历的时候会把未遍历到的0的位置改变,导致缺失,贴代码。

class Solution {
public:
    void moveZeroes(vector<int>& nums) 
    {
        int n = nums.size();
        int temp;
        for(int i = n-2 ; i >=0 ; i--)
        {
            if(nums[i] == 0)
            {
                for(int j = i ; j <n-1 ; j++)
                {
                    swap(nums[j],nums[j+1]);              
                }
            }
        }  
    }
};

nnd,双指针很巧妙,以0为标准,将所有不是0的数放到0的左边,0都放到右边,解决问题,贴代码

class Solution {
public:
    void moveZeroes(vector<int>& nums) 
    {
        int n = nums.size();
        int right = 0;
        int left = 0;
        while(right<n)
        {
            if(nums[right])
            {
                swap(nums[right],nums[left]);
                left++;
            }
            right++;
        }
    }
};

这种解法有一个问题就是会有很多无效操作,如前几个元素都不为0的话,要每个元素和自己交换一下,是废操作。想了一下,可以每次遍历,找到当前第一个0,以及这个0之后的第一个非零数,进行交换。

 

上一篇:LeetCode 283. 移动零


下一篇:130-283. 移动零