专栏首页算法channel我对一道常考面试题的详细分析

我对一道常考面试题的详细分析

移动零

题目

给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。

示例:

输入: [0,1,0,3,12]

输出: [1,3,12,0,0]

说明:

  1. 必须在原数组上操作,不能拷贝额外的数组。
  2. 尽量减少操作次数

分析

必须在原数组上操作,不能拷贝额外的数组;同时尽量减少操作次数,说白了就是想叫我们写出更好的算法。

如何分析?

观察

输入: [0,1,0,3,12]

输出: [1,3,12,0,0]

整个过程就是0元素不断后移,非零元素不断前移的过程,所以算法每步操作的目标便是:逐渐达成这个分布规律

怎样优化操作?

假设两个指针slowfast分别指向连续零区间的第一个0,最后一个0的后一个位置,如下图所示:

那么,fast-slow 正是索引从0~fast区间范围内0元素的个数。

fast指向下一个元素:

若打问号元素为0,根据每步操作的目标是非零元素前移,零元素后移。所以迭代到此处时它已经为0元素,所以至少肯定不用前移,那么就保持原地不动。

若打问号的元素取值非0,根据每步操作的目标是非零元素前移,零元素后移。因为slow~fast这块都为0,所以为了目标,非零元素要和第一个0交换,这样不就实现非零元素前移,零元素后移的目标了吗

交换后:

你看确实前进一步了吧。

求解代码

以上分析过程就是此问题的一个中间状态的操作分析,是从第i次迭代状态到第i+1次迭代状态的变化过程。

有了这个状态更新方程,因此就会很自然的写出下面的代码:

class Solution(object):
    def moveZeroes(self, nums):
        fast,slow=0,0 # 分别指向连续零区间的最右侧、最左侧
        while fast<len(nums):
            # if nums[fast]==0 do nothing 
            if nums[fast]!=0:
                # if fast == slow shows zero isn't found yet
                if fast > slow:# zero exists
                    nums[slow], nums[fast] = nums[fast], 0
                slow += 1
            fast += 1   

S1,设定两个指针初始分别指向第一个元素:

S2,第一个元素等于0,仅fast前进1步:

S3, 下一次迭代时,fast指向元素不为0,则交换:

同时slowfast同时都前进一步:

S4,此时元素等于0,此情况重复步骤S2,因此重复上面操作。

依次类推,罗列出中间的各个状态:

fast到头,程序结束。

可以看到slow指向连续零区间的第一个0,fast指向连续零区间的最后一个0的后一个位置。

这与文章中分析中间状态的过程一脉相承,验证分析过程是准确的。

Day1-Day35 刷题总结的思维导图

本文分享自微信公众号 - Python与机器学习算法频道(alg-channel),作者:振哥

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-07-01

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Matplotlib绘制的50类图 ,足够惊艳!

    double
  • Leetcode|Find K Closest Elements

    01 — 题目 Given a sorted array, two integers k and x, find the k closest elements ...

    double
  • 弄懂这 6 个问题,拿下 Python 生成器!

    施工计划第17篇。公众号真正做技术写作的本来就少,能够从一而终,始终坚持下去的,更是凤毛麟角,我会向我心中那些正真在做技术分享的前辈们学习,争取早日加入这类俱乐...

    double
  • 漫画:三次反转旋转数组(一次修订版)

    第189题:给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。

    程序员小浩
  • 漫画:三次反转旋转数组

    第189题:给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。

    程序员小浩
  • LeetCode 80,不使用外部空间的情况下对有序数组去重

    今天是LeetCode专题的第49篇文章,我们一起来看LeetCode的第80题,有序数组去重II(Remove Duplicates from Sorted ...

    TechFlow-承志
  • Python的系统管理_06_pytho

    res =subprocess.Popen(['uname','-sv'],stdout=subprocess.PIPE)

    py3study
  • 这本4.8分期刊上13篇中国学者论文被同一人指出存在问题,4篇文章作者已回应

    说起学术打假人,大家应该都知道Elizabeth Bik,从她手上举报过无数大牛。但现在Pubpeer等学术打假网站上也出现了不少新人,Indigofera T...

    百味科研芝士
  • 揭秘上了腾讯财报的QQ卡通画

    动漫是想象的艺术,燃烧了大部分人的青春,通过人工智能让用户见到二次元的自己,是个兼具科技性、艺术性、娱乐性和商业性的课题。下面将由腾讯光影研究室的同学,来帮忙...

    天天P图攻城狮
  • Leetcode打卡 | No.26 删除排序数组中的重复项

    欢迎和小詹一起定期刷leetcode,每周一和周五更新一题,每一题都吃透,欢迎一题多解,寻找最优解!这个记录帖哪怕只有一个读者,小詹也会坚持刷下去的!

    小小詹同学

扫码关注云+社区

领取腾讯云代金券