摘要:尽量减少操作次数。样例如样例所示,数组,移动完成后变成,下面来讲解双指针的做法。这样我们就完成了元素的移动,同时也保持了非元素的相对顺序。
给定一个数组 nums
,编写一个函数将所有 0
移动到数组的末尾,同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12]输出: [1,3,12,0,0]
说明:
(双指针) O ( n ) O(n) O(n)
给定一个数组 nums
,要求我们将所有的 0
移动到数组的末尾,同时保持非零元素的相对顺序。
样例:
如样例所示,数组nums = [0,1,0,3,12]
,移动完成后变成nums = [1,3,12,0,0]
,下面来讲解双指针的做法。
我们定义两个指针,i
指针和k
指针,i
指针用来遍历整个nums
数组,k
指针用来放置nums
数组元素。然后将非0
元素按照原有的相对顺序都放置到nums
数组前面,剩下的位置都置为0
。这样我们就完成了0
元素的移动,同时也保持了非0
元素的相对顺序。
具体过程如下:
i
和k
,初始化i = 0
,k = 0
。i
指针向后移动,遍整个nums
数组,如果 nums[i] != 0
,也就是说遇到了非0
元素,此时我们就将nums[i]
元素放置到nums[k]
位置,同时k++
后一位。k
位置之后的元素都赋值为0
。实现细节:
遍历数组可以使用for(int x : nums)
,这样就少定义一个指针,代码也显得更加简洁。
时间复杂度分析: O ( n ) O(n) O(n) , n n n是数组的长度,每个位置只被遍历一次。
时间复杂度分析: O ( 1 ) O(1) O(1) ,只需要常数的空间存放指针变量。
class Solution {public: void moveZeroes(vector<int>& nums) { int k = 0; for(int x : nums) if(x != 0) nums[k++] = x; while(k < nums.size()) nums[k++] = 0; }};
class Solution { public void moveZeroes(int[] nums) { int k = 0; for(int x : nums) if(x != 0) nums[k++] = x; while(k < nums.length) nums[k++] = 0; }}
原题链接: 283. 移动零
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/119014.html
摘要:题目链接题目分析给定一个整数数组,将值为的元素移动到数组末尾,而不改动其他元素出现的顺序。再在去后的元素末尾填充到计算出的数组长度。最终代码若觉得本文章对你有用,欢迎用爱发电资助。 D68 283. Move Zeroes 题目链接 283. Move Zeroes 题目分析 给定一个整数数组,将值为0的元素移动到数组末尾,而不改动其他元素出现的顺序。 思路 计算总共有多少个元素。 再...
摘要:给定一个数组,编写一个函数将所有移动到数组的末尾,同时保持非零元素的相对顺序。尽量减少操作次数。换个思路,把非数字前移,不去管数字。这样遍历完之后,数组索引从到之间的数值即为所求得保持非零元素的相对顺序,而之后的数值只需要全部赋值即可。 给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。 Given an array nums, write ...
摘要:给定一个数组,编写一个函数将所有移动到数组的末尾,同时保持非零元素的相对顺序。尽量减少操作次数。换个思路,把非数字前移,不去管数字。这样遍历完之后,数组索引从到之间的数值即为所求得保持非零元素的相对顺序,而之后的数值只需要全部赋值即可。 给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。 Given an array nums, write ...
摘要:月下半旬攻略道题,目前已攻略题。目前简单难度攻略已经到题,所以后面会调整自己,在刷算法与数据结构的同时,攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题,目前已攻略 100 题。 一 目录 不折腾的前端,和咸鱼有什么区别...
摘要:第五题对称二叉树难度简单给定一个二叉树,检查它是否是镜像对称的。第十六题最大连续的个数难度简单给定一个二进制数组,计算其中最大连续的个数。第十八题平方数之和难度简单给定一个非负整数,你要判断是否存在两个整数和,使得。 写在前面 最近忙着调教新装备,没有及时的写题解,但是没有在偷懒没刷题喔~来认真整理下最近做的题目~ 之前考虑按tag来刷题,后来收到了推荐的leetcode题解,就根据上...
阅读 800·2021-11-18 10:07
阅读 2292·2021-10-14 09:42
阅读 5174·2021-09-22 15:45
阅读 556·2021-09-03 10:29
阅读 3431·2021-08-31 14:28
阅读 1841·2019-08-30 15:56
阅读 3008·2019-08-30 15:54
阅读 966·2019-08-29 11:32