给定一个数组 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 nn是数组的长度,每个位置只被遍历一次。
**时间复杂度分析:**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://blog.csdn.net/weixin_45629285/article/details/120057025
内容来源于网络,如有侵权,请联系作者删除!