关关的刷题日记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教程资料

原文发布于微信公众号 - 专知(Quan_Zhuanzhi)

原文发表时间:2017-09-24

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏守候书阁

js数组操作--使用迭代方法替代for循环

数组的迭代方法,这个想必大家都不陌生了,可能刚入门的人暂时还没接触到这个。但是以后的开发中,肯定会用得上的。我自身的一个使用经历就是,如果迭代方法用的适当,不但...

16030
来自专栏小樱的经验随笔

2017"百度之星"程序设计大赛 - 复赛1001&&HDU 6144 Arithmetic of Bomb【java大模拟】

Arithmetic of Bomb Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768...

33270
来自专栏HansBug's Lab

3404: [Usaco2009 Open]Cow Digit Game又见数字游戏

3404: [Usaco2009 Open]Cow Digit Game又见数字游戏 Time Limit: 3 Sec  Memory Limit: 128 ...

29490
来自专栏一个会写诗的程序员的博客

《Kotin 极简教程》第7章 面向对象编程(OOP)(1)第7章 面向对象编程(OOP)《Kotlin极简教程》正式上架:

在前面的章节中,我们学习了Kotlin的语言基础知识、类型系统、集合类以及泛型相关的知识。在本章节以及下一章中,我们将一起来学习Kotlin对面向对象编程以及函...

10120
来自专栏专知

【Leetcode 303】关关的刷题日记67–Leetcode 303 Range Sum Query – Immutable

关关的刷题日记67 – Leetcode 303 Range Sum Query – Immutable 题目 Given an integer array n...

31680
来自专栏人工智能LeadAI

记一道未能答出的算法面试题

昨天晚上,参加了一场面试,有道算法题当时没答出来,痛心疾首!刚刚起床给娃娃换尿布的空当,突然间就想清楚了实现的办法,当时没答出来就是卡在构建多叉树这一点!本文会...

39670
来自专栏专知

关关的刷题日记82 – Leetcode 453. Minimum Moves to Equal Array Elements

关关的刷题日记82 – Leetcode 453. Minimum Moves to Equal Array Elements 题目 Given a non-e...

30150
来自专栏marsggbo

(原创)详解KMP算法

KMP算法应该是每一本《数据结构》书都会讲的,算是知名度最高的算法之一了,但很可惜,我大二那年压根就没看懂过~~~ 之后也在很多地方也都经常看到讲解KMP算法的...

27670
来自专栏海天一树

NOIP 2018提高组初赛C/C++答案详解

分析: 二进制化八进制:从低位(右)往高位(左),每三位直接换成八进制即可。 (1001101011)2 = (10 0110 1011)2 = (26B)...

32840
来自专栏大大的微笑

设计模式之代理模式

       代理模式是一种注重过程的一种模式,在我们做某一具体事情之前或之后做一些辅助性的工作; 好处是将辅助工作从主要工作中抽离出来,但是又能协同工作, ...

235100

扫码关注云+社区

领取腾讯云代金券