当前位置：首页 > news >正文

【LeetCode】用双指针解决移除元素问题、合并两个有序数组求解

news 2025/6/30 8:16:27

🔥个人主页：艾莉丝努力练剑

❄专栏传送门：《C语言》、《数据结构与算法》、C语言刷题12天IO强训

🍉学习方向：C/C++方向

⭐️人生格言：为天地立心，为生民立命，为往圣继绝学，为万世开太平

前言：牛客网和LeetCode的刷题都不可或缺，我们都要做一做，无论是参加竞赛还是笔试面试，至少能提升你的代码能力！洛谷的题目也可以去做一做。力扣的题目对提升代码能力很有帮助，需要有一点基础，几乎都是接口型的题目，关于接口型和IO型的区别我们在本专栏的第一篇【LeetCode】力扣题——轮转数组、消失的数字、数组串联中就介绍过了，这里不再赘述。

正文

LeetCode有题解功能，今天给大家带来的两道题博主都写了题解，链接放在题目链接下面了。

一、移除元素

1、题目描述

题目链接：27. 移除元素

博主的力扣题解：用双指针解决移除元素问题且时间复杂度O(n)空间复杂度O(1)

2、思考

和轮转数组那道题有些类似，本题我们也有三种思路：

思路（1）：嵌套

这里写出来循环嵌套，时间复杂度达到了O(n^2)，太大了，如果这个数组的绝大部分数据都是val，这个复杂度就太low了，这个思路就直接可以out了。

思路（2）：空间换时间

是不是感觉似曾相识？没错。我们介绍轮转数组的三种思路时说的第二种方法就是空间换时间。

我们的做法是（当然上图中博主已经标注出来了）：我们创建一个新的数组，我们遍历过程中，把不是val的数据，放到新数组，再把新数组的值拷贝到原数组。这个思路的时间复杂度和空间复杂度都是O(n)，能不能保证不创建新的数组的情况下，还能让时间复杂度O(n)而且空间复杂度O(1)？

思路（3）：双指针

我们的解题过程是：先创建两个指针变量src和dst，两个指针从左往右遍历数组，分两种情况：

（1）当src位置不是val的值（即不是val），把src位置给dst，随后src++、dst++；

（2）当src为止是val的值（即val），src++。

3、求解

之前在【数据结构与算法】专栏中的【数据结构与算法】数据结构初阶：详解顺序表和链表（二）这篇文章中我们提了一嘴（当然在铸币主包写LeetCode题解博客的时候，那篇文章还没发，只是写完了，不过主包马上就会发的，大家请等一等！）前置++和后置++，说在同一个函数里面，前置后置因为现代计算机算力的强大基本上区别不大，这里我们就可以看出两者的区别啦。

我们既然想出了时间复杂度O(n)空间复杂度O(1)的解法，那我们就用这种思路写一下代码。

int removeElement(int* nums, int numsSize, int val) 
{int dst = 0;int src = 0;while(src < numsSize){if(nums[src] != val){nums[dst] = nums[src];src++;dst++;}else{src++;}}return dst;
}

我们后置++是和前面赋值的代码分开写的，结合代码的逻辑，两者可以合并一下，写成这样：

//也可以直接在前面后置++，体现了后置++的用法
int removeElement(int* nums, int numsSize, int val) 
{int dst = 0;int src = 0;while(src < numsSize){if(nums[src] != val){nums[dst++] = nums[src++];}else{src++;}}return dst;
}

复杂度：时间复杂度: O(n)，空间复杂度: O(1)。

二、合并两个有序数组

题目链接：88. 合并两个有序数组

博主的力扣题解：双指针求解合并两个有序数组（利用有序的特性）

1、题目描述

2、思考

这个方法具体怎么运用？我们可以利用有序的特性，我们从后往前放，即两个数组nums1、nums2

我们取大的从后往前放，两个一样大，随便放一个，这里从后往前按顺序放2。这里有两种情况：

（1）在这里如果nums1还剩几个数据就不用管了；

（2）还有一种情况，如果是nums2还剩几个数据呢？

我们先比，注意——我们只要有值的两个数比，0是不参与的，比完了把大的那个从后往前依次放进去，nums1的放完了，nums2剩下的依次从后往前放。

3、求解

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) 
{int end1 = m - 1;int end2 = n - 1;int end = m + n - 1;while(end1 >= 0 && end2 >= 0){if(nums1[end1] > nums2[end2]){nums1[end] = nums1[end1];--end;--end1;}else{nums1[end] = nums2[end2];--end;--end2;}}//如果是end1，不需要处理，也就是在nums1里面while(end2 >= 0){nums1[end] = nums2[end2];--end;--end2;}
}

复杂度：时间复杂度: O(m+n)，空间复杂度: O(1)。