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);
}提交结果
