L28.【LeetCode笔记】移动零(三种解法)
目录
1.题目
2.向前覆盖法
分析
代码
提交结果
3.优解:双指针
代码
提交结果
4.其他不符合题意的方法:使用队列
代码
提交结果
1.题目
https://leetcode.cn/problems/move-zeroes/description/
给定一个数组
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进阶：你能尽量减少完成的操作次数吗？
2.向前覆盖法
分析
设一指针ptr,从头到尾遍历数组,发现num[ptr]==0时,执行向前覆盖,尾部填充一个0,但如果只这样写会有问题!
例如测试数据[0,0,1,0]
移动一次后发现1前面的元素nums[ptr-1]==0,即没有完全移动好1,那么这种情况出现时ptr要--
写成下面这样可以吗?
if (nums[ptr-1]==0)ptr--;不行会有潜在的越界风险! ptr-1可能会<0,因此要写成
if (ptr>=1&&nums[ptr-1]==0)ptr--;代码
void moveZeroes(int* nums, int numsSize)
{int ptr=0;while(ptr<=numsSize-1){if (ptr>=1&&nums[ptr-1]==0)ptr--;if (0==nums[ptr]){ for (int i=ptr;i<numsSize-1;i++){nums[i]=nums[i+1];}nums[numsSize-1]=0;numsSize--;} ptr++;}
}提交结果
3.优解:双指针
LeetCode官方题解的双指针有点不好理解,其实可以直接分类讨论指针所指向的值:设两个指针prev和cur,当初始prev==0,cur==1时(先排除数组元素只有一个的情况),它们指向元素的情况无非就四种
1.nums[prev]==0,nums[cur]==0
2.nums[prev]!=0,nums[cur]==0
3.nums[prev]!=0,nums[cur]!=0
4.nums[prev]==0,nums[cur]!=0
首先看4:这种情况最好处理,nums[prev]交换nums[cur]就能将0向后移动
剩下情况1,情况2,情况3都要遵循一个原则:想方设法转换为情况4
情况1:nums[prev]==0,nums[cur]==0 --转换--> nums[prev]==0,nums[cur]!=0 :cur++寻找nums[cur]!=0
情况2:nums[prev]!=0,nums[cur]==0 --转换--> nums[prev]==0,nums[cur]!=0 :prev和cur都++
情况3:nums[prev]!=0,nums[cur]!=0 --转换--> nums[prev]==0,nums[cur]!=0 :附近没有0,prev和cur都++
代码
void moveZeroes(int* nums, int numsSize)
{if(numsSize==1)return;int prev=0;int cur=1;while (cur<numsSize){if (nums[prev]==0&&nums[cur]!=0){int tmp=nums[prev];nums[prev]=nums[cur];nums[cur]=tmp;}if (nums[prev]!=0&&nums[cur]!=0){prev++;}if (nums[prev]!=0&&nums[cur]==0){prev++;}cur++;}
}
提交结果
4.其他不符合题意的方法:使用队列
虽然使用队列并没有原地对数组操作,但可以锻炼对队列的使用(其实直接开辟一个临时数组就行)
思想:将非0数字依次入队,遍历完一遍数组后再依次出队,原数组末尾补0
有关队列的文章参见:98.【C语言】数据结构之队列
代码
typedef int QDataType;typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;int size;
}Queue;void QueueInit(Queue* pq)
{pq->head = pq->tail = NULL;pq->size = 0;
}void QueueDestroy(Queue* pq)
{QNode* cur = pq->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;pq->size = 0;
}void QueuePush(Queue* pq, QDataType x)
{QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc");return;}newnode->data = x;newnode->next = NULL;if (pq->head == NULL){assert(pq->tail == NULL);pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}void QueuePop(Queue* pq)
{QNode* next = pq->head->next;free(pq->head);pq->head = next;if (pq->head == NULL)pq->tail = NULL;pq->size--;
}bool QueueEmpty(Queue* pq)
{return pq->size == 0;
}QDataType QueueFront(Queue* pq)
{return pq->head->data;
}void moveZeroes(int* nums, int numsSize)
{Queue q;QueueInit(&q);for (int i=0;i<numsSize;i++){if (nums[i]!=0){QueuePush(&q,nums[i]);}}int j=0;while(!QueueEmpty(&q)){nums[j]=QueueFront(&q);QueuePop(&q);j++;}for (;j<numsSize;j++){nums[j]=0;}QueueDestroy(&q);
}提交结果
