C语言每日一题（62）移动零
题目链接
题目描述
给定一个数组 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
进阶：你能尽量减少完成的操作次数吗？
思路分析
知识点：双指针
解析：
实现本功能有两种方法：
方法1:计数器
定义两个指针cur和prev，从最左边开始，如果nums【cur】==0的话，cur往下走，此时定义一个计数器记录0的个数，当nums【cur】不为0时，就将该值赋给prev的位置，之后prev往下走，cur也往下走，直到cur越界，此时prev指向的位置就是需要赋值0的位置。
之前用上的计数器，利用它进入循环，从prev开始，赋值0即可。
void moveZeroes(int* nums, int numsSize) {
int prev=0;
int cur=0;
int count=0;
if(numsSize==1&&nums[0]==0)
{
return;
}
else
{
while(cur<numsSize)
{
if(nums[cur]==0)
{
count++;
}
else
{
nums[prev]=nums[cur];
prev++;
}
cur++;
}
for(int i=0;i<count;i++)
{
nums[prev+i]=0;
}
}
}时间复杂度：cur遍历一次后，prev还要继续遍历一次，O（n）
空间复杂度：O（1）
上面的方法需要遍历两次，下面的方法只需要遍历一次
方法2.前后指针法(一次遍历）
同样定义两个指针prev和cur，当cur的值等于0时，cur就往下走，直到cur不等于0时，此时它与prev的间隔数就是0的个数，将cur的值于prev的值交换，然后prev往下走，直到cur越界完成
void Swap(int* a, int* b) {
int tmp = *a;
*a = *b;
*b = tmp;
}
void moveZeroes(int* nums, int numsSize) {
if (numsSize == 1 && nums[0] == 0) {
return;
} else {
int prev = 0;
int cur = 0;
while (cur < numsSize) {
if (nums[cur] != 0) {
Swap(&nums[cur], &nums[prev++]);
}
cur++;
}
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2024-03-08，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录