1.前言
在之前，我们学习了顺序表的概念与实现，其基本概念如下：
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，是线性表中的一种，分为静态顺序表和动态顺序表。一般情况下采用数组存储，支持元素的随机访问。在数组上完成数据的增删查改。
而本期，我们将通过两道在线OJ题来巩固顺序表的基础知识，这两道题分别来自LeetCode 27移除元素和LeetCode 88合并两个有序数组。
2.移除元素
1.题目
2.初步分析
第一眼我们的想法可能是再开辟一个新数组，然后遍历原数组，把不等于val的数值放入新数组中即可完成移除。过程如下：
但是这样的空间复杂度为O(N)，不符合题目的要求，题目要求我们原地移除元素。
我的思路是：将数组中不等于val的值移到数组前面。定义两个变量left和right用来表示数组的下标，right向后遍历数组，当nums[right]不为val时，则将nums[right]赋值给nums[left]，然后left++、right++，否则right++，循环直到right等于数组长度。其空间复杂度为O(1)。动图过程如下：
我们发现，最后left前的元素即为我们需要的数组元素，且left即为移除后元素个数
3.代码实现
-
//接口型OJ
-
int removeElement(int* nums, int numsSize, int val)
-
{
-
int right =
0;
-
int left =
0;
-
for (right =
0; right < numsSize; right++)
//右指针遍历一遍数组
-
{
-
if (nums[right] != val)
//不为val就往前放
-
{
-
nums[left] = nums[right];
-
left++;
//左指针右移
-
}
-
}
-
return left;
//left即为移除后所需元素个数
-
-
}
3合并两个有序数组
1.题目
2.初步分析
本题的目的是将两个有序数组从小到大归并到一个数组中。我们依旧可以遍历两个数组的元素进行对比，将满足条件的元素放入归并后数组中。但是由于题目要求将nums1和nums2数组归并到nums1中，所以我们不能从左往右遍历两个数组，将小的放入nums1中，否则会出现以下情况：
显然，这样做显然会造成nums1的数据丢失，导致出错。
我的思路是：我们可以发现，由于nums1的数组空间是m+n，所以后面n个空间是空的。我们可以利用这个特点，从右往左反向遍历数组，将元素进行比较，较大者放于数组后面，从后往前放，如下：
这个算法需要注意的是：循环的结束条件是end1和end2其中一个小于0 ，当end2先小于零时，说明我们已经按照顺序将num2数组的元素全部归入num1了，就无需再做处理。但当num1先小于零时，此时nums2数组的数据并未全部归并到nums1中，我们还需将nums2剩余元素放入nums1中。此算法的时间复杂度为O(M+N)。
3.AC代码实现
-
//接口型OJ
-
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
-
{
-
int end1 = m -
1;
-
int end2 = n -
1;
-
int end = nums1Size -
1;
-
while (end1 >=
0 && end2 >=
0)
//双指针，从后往前找最大元素
-
{
-
//将最大元素放入nums1数组后面
-
if (nums1[end1] > nums2[end2])
-
{
-
nums1[end] = nums1[end1];
-
end1--;
-
end--;
-
}
-
else
-
{
-
nums1[end] = nums2[end2];
-
end2--;
-
end--;
-
}
-
}
-
while (end2 >=
0)
//如果nums1先遍历结束，需要将nums2剩余数据放入nums1
-
{
-
nums1[end] = nums2[end2];
-
end2--;
-
end--;
-
}
-
-
}
以上，就是顺序表刷题的全部内容。
制作不易，能否点个赞再走呢qwq
转载：https://blog.csdn.net/m0_69909682/article/details/128896430