Leetcode 283:移动零(最详细解决方案)
发布日期:2021-06-29 16:00:43
浏览次数:2
分类:技术文章
本文共 2507 字,大约阅读时间需要 8 分钟。
给定一个数组 nums
,编写一个函数将所有 0
移动到数组的末尾,同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12]输出: [1,3,12,0,0]
说明:
- 必须在原数组上操作,不能拷贝额外的数组。
- 尽量减少操作次数。
解题思路
我们首先想到的做法是:遍历一遍数组nums
,将非0
元素添加到一个新建立的数组nonZeroElements
中,然后将nonZeroElements
中的元素copy
到nums
的最前面,对nums
后面的元素赋值0
即可。
class Solution: def moveZeroes(self, nums): """ :type nums: List[int] :rtype: void Do not return anything, modify nums in-place instead. """ nonZeroElements = [] for i in nums: if i != 0: nonZeroElements.append(i) nonZeroElements_len = len(nonZeroElements) for i in range(nonZeroElements_len): nums[i] = nonZeroElements[i] nums_len = len(nums) for i in range(nonZeroElements_len, nums_len): nums[i] = 0
那么我们稍微分析一下这个解法,我们发现这个解法中使用了一个额外的辅助空间,那么我们能不能不使用额外空间呢?Yes。
我们可以使用一个变量k
记录位置,我们通过遍历nums
数组,将不为0
的元素依次复制到nums
的前面,并且记录我们复制了多少个元素,对len(nums)-k
的元素置0
即可。
class Solution: def moveZeroes(self, nums): """ :type nums: List[int] :rtype: void Do not return anything, modify nums in-place instead. """ k = 0 for i in nums: if i != 0: nums[k] = i k += 1 nums_len = len(nums) for i in range(k, nums_len): nums[i] = 0
通过上面的方法,我们将算法的空间复杂度降到了O(1)
级别,而算法的时间复杂度依旧是O(n)
级别。
当然我们这里有一个更pythonic
的做法
class Solution: def moveZeroes(self, nums): """ :type nums: List[int] :rtype: void Do not return anything, modify nums in-place instead. """ for j in range(nums.count(0)): nums.remove(0) nums.append(0)
但是从效率上远不及前面的做法。
我们看到上面的做法都是对非0
元素和0
元素分开考虑,那们我们可不可以对这两种元素同时考虑呢?我们通过不断的交换非0
元素和0
元素之间的位置做到这一点。
class Solution: def moveZeroes(self, nums): """ :type nums: List[int] :rtype: void Do not return anything, modify nums in-place instead. """ k = 0 for i, num in enumerate(nums): if num != 0: nums[i], nums[k] = nums[k], nums[i] k += 1
上面的代码比之前的简洁了不少,但是依然还有可优化的空间。如果我们的数组全部是非0
元素的话,上面代码就会对所有非0
元素自己交换一次。所有可以有如下改进:
class Solution: def moveZeroes(self, nums): """ :type nums: List[int] :rtype: void Do not return anything, modify nums in-place instead. """ k = 0 for i, num in enumerate(nums): if num != 0: if i != k: nums[i], nums[k] = nums[k], nums[i] k += 1
实际上这里的思想是借鉴了。
该问题的其他语言版本添加到了我的
如有问题,希望大家指出!!!
转载地址:https://coordinate.blog.csdn.net/article/details/80475808 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
哈哈,博客排版真的漂亮呢~
[***.90.31.176]2024年04月14日 00时51分51秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
el-table 二维数组合并行
2019-04-29
UR5e机械臂运行一直阻塞在waitForServer
2019-04-29
ROS把pkg1下的某个头文件和源文件生成动态链接库供pkg2调用
2019-04-29
使用urdf_tutorial快速可视化urdf文件
2019-04-29
SQl 数据完整性(随堂博客)
2019-04-29
左连接、右连接、内连接
2019-04-29
MySQL DQL语句基础(随堂博客)
2019-04-29
利用MySQL进行数据复杂查询(1)
2019-04-29
MySQL 表与表之间的关系
2019-04-29
pymysql 的基础应用
2019-04-29
Python 管理程序改进——连接MYSQL
2019-04-29
Python 爬虫-豆瓣影星图片下载
2019-04-29
网页端数据库操作界面—主题函数文件
2019-04-29
网页端数据库操作界面-Html页面(1)
2019-04-29
Python爬虫 百度热搜热点
2019-04-29
excel的常用函数(二)
2019-04-29
excel文本函数
2019-04-29
电商大战二十年
2019-04-29