算法题丨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.
Note:
1.You must do this in-place without making a copy of the array.
2.Minimize the total number of operations.
示例
Given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].
算法分析
难度:低
分析:给定一个数组,将所有为0的元素都移动到数组的末尾,并保持非0的元素排序保持不变。
思路:首先,思考满足第1个条件很简单,就是遍历数组,判断当前元素是否为0,如果是0,将0跟当前元素互换一下,遍历完数组就可以了。但是这样处理的话,并不能保证非0元素排序不变,所以,我们放弃这种思路。
那怎么保持非0元素的排序呢?我们考虑记录当前非0的个数索引index,遍历的时候,如果是非0元素,将数组[index]记录该元素,非0的个数索引index加1,下一个非0的就会记录在数组[index+1]中,依次类推,这样其实实现了非0元素顺序保存。最终数组[0,index)即为保持排序的非0元素。剩下的就很简单了,将数组[index]之后的元素全部置0就可以了。
代码示例(C#)
public void MoveZeroes(int[] nums) { int index = 0; for (int i = 0; i < nums.Length; ++i) { if (nums[i] != 0) { //非0元素,记录排序 nums[index++] = nums[i]; } } //非0元素之后的元素全置0 for (int i = index; i < nums.Length; ++i) { nums[i] = 0; } }
复杂度
- 时间复杂度:O (n).
- 空间复杂度:O (1).
附录
文章作者:原子蛋
文章出处:https://www.cnblogs.com/lizzie-xhu/
个人网站:https://www.lancel0t.cn/
个人博客:https://blog.lancel0t.cn/
微信公众号:原子蛋Live+
扫一扫左侧的二维码(或者长按识别二维码),关注本人微信公共号,获取更多资源。
本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
算法题丨Remove Element
描述 Given an array and a value, remove all instances of that value in-place and return the new length. Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory. The order of elements can be changed. It doesn't matter what you leave beyond the new length. 示例 Given nums = [3,2,2,3], val = 3, Your function should return length = 2, with the first two elements of nums being 2. 算法分析 难度:低分析:给定数组和指定一个目标值,从数组中移除所有跟目标值相等的元素,返回最终元素的长度,注意不要...
- 下一篇
Python_(1)数据类型及其常见使用方法(图文)
python学习笔记 一. 变量类型及其常见函数用法:数值型(int float complex) 字符串 (str) 列表 (list)元组 (tuple) 字典(dict) (1)数值 import math a=20;b=3.2; a**3; #结果为20*20*20《=》math.pow(20,3) print(a**3); print(round(100/3,3)); #小数点后面保留3位有效数字(保证输出格式) print(math.ceil(3.32)); #向上取整 print(math.floor(3.32)); #向下取整 print(math.radians(180)); #度数转换成弧度制 divmod(10); #取商和余数 结果:8000 33.333 4 3 3.1415926 (3,1) (2)字符串 str="abc";str1="def"; print(a+b); #字符串拼接 print(a*3); #字符串乘法 结果:abcdef abcabcabc (3)元组 (元组只要确定就不能修改 增加 删除任何元素) zoo=('wolf','dog',...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- MySQL8.0.19开启GTID主从同步CentOS8
- SpringBoot2全家桶,快速入门学习开发网站教程
- CentOS8编译安装MySQL8.0.19
- CentOS8,CentOS7,CentOS6编译安装Redis5.0.7
- CentOS7,CentOS8安装Elasticsearch6.8.6
- Red5直播服务器,属于Java语言的直播服务器
- CentOS8安装MyCat,轻松搞定数据库的读写分离、垂直分库、水平分库
- SpringBoot2整合MyBatis,连接MySql数据库做增删改查操作
- CentOS6,CentOS7官方镜像安装Oracle11G
- Jdk安装(Linux,MacOS,Windows),包含三大操作系统的最全安装