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);
}

 提交结果