关关的刷题日记04——Leetcode 283. Move Zeroes

题目

283. Move Zeroes

Given an array nums, write a function to move all 0’s to the end of it while maintaining the relative order of the non-zero elements.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0]. Note: You must do this in-place without making a copy of the array. Minimize the total number of operations.

题目的意思说是将数组中所有的0移动到数组尾部，但是要保持其他非零元素的相对顺序。要求只能在数组上进行操作，不能新建其他数组。

方法

思路：不能新建其他数组，所以只能原地移动。从头至尾遍历数组，每当遇到0，就和它后面第一个非0元素互换位置。直到非0元素是数组的最后一个数，就可以提前结束循环了。还有一点需要注意的是题目要求总的操作次数最小，所以要用一个flag来标记上一次找到的不为零的数的位置，下一次就从这个数的后面开始找就可以了，因为此时上一个被交换的数到当前这个数之间肯定全部是0了。移动顺序如下： [0, 1, 0, 3, 12] [1, 0, 0, 3, 12] [1, 3, 0, 0, 12] [1, 3, 12, 0, 0]

代码如下：

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

以上就是关关关于这道题的总结经验，希望大家能够理解，有什么问题可以在我们的专知公众号平台上交流或者加我们的QQ专知-人工智能交流群 426491390，也可以加入专知——Leetcode刷题交流群（请先加微信小助手weixinhao: Rancho_Fang）。

欢迎大家使用专知！访问专知，搜索主题-LeetCode，获取更多关于LeetCode教程资料。