关关的刷题日记04 – Leetcode 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了。

时间复杂度O(n2).

移动顺序如下：

[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）。 同时请，关注我们的公众号，获取最新关于专知以及人工智能的资讯、技术、算法等内容。扫一扫下方关注我们的微信公众号。