每日一题学习笔记——移动零
给定一个数组 nums
,编写一个函数将所有 0
移动到数组的末尾,同时保持非零元素的相对顺序。
请注意 ,必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums =[0,1,0,3,12]
输出:[1,3,12,0,0]
示例 2:
输入: nums =[0]
输出:[0]
提示:
1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int n=nums.size();
int count=0;
vector<int> res;
for(int i=0;i<n;i++){
if(nums[i]!=0){
res.push_back(nums[i]);
}else{
count++;
}
}
for(int i=0;i<count;i++){
res.push_back(0);
}
nums=res;
}
};
新开一个数组的思路很简单,就是先添加不为0的数,同时计算有多少个零,然后添加到数组最后就可以了。时间复杂度基本为0,但是空间复杂度很高。而且题目要求在原数组上进行操作,因此我们还是采用双指针的思路。
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int n=nums.size();
int l=0;
int r=0;
while(r<n){
if(nums[r]){
swap(nums[l],nums[r]);
l++;
}
r++;
}
}
};
在不改变时间复杂度的情况下,降低了空间复杂度。思路也很简单,l指针永远指向第一个为0的位置,而r指针去遍历数组中的位置。