数据结构初步（四）- oj练习-线性表之顺序表
数据结构初步（四）- oj练习-线性表之顺序表
前言
前面学习了顺序表的相关概念后，让我们来会会这几个题！
1. 移除元素
1.1 题目链接
力扣（LeetCode）链接：移除元素
1.2 题目要求
给你一个数组
和一个值
，你需要 原地 移除所有数值等于
的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用
额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
说明:
为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
//
是以“引用”方式传递的。也就是说，不对实参作任何拷贝
;
// 在函数里修改输入数组对于调用者是可见的。 // 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
1.3 代码框架
int removeElement(int* nums, int numsSize, int val){
}1.4 思路分析
给定一个数组
，遇到与
的数组元素相等就去掉，不相等就保留，假设
是数组
中与
相等元素的个数，则修改后的数组前
个位置是存放非
的有效位置。
题目要求空间复杂度是
，不能开辟额外的临时数组空间。
我们可以把题目所给的原数组
当作修改元素后的新数组，两个变量记录数组下标，假设
记录原数组下标，
记录新数组下标；
记录原数组中与
相等的元素个数。
开始时
的下标都是
，分别对应新旧数组的第一个位置，如果
位置的元素等于
，
均往后后移动一位；否则，就把
位置元素放入
位置处，然后
往后移动一位。直到旧数组被
遍历一遍。
时间复杂度
空间复杂度
1.5 代码实现
int removeElement(int* nums, int numsSize, int val){
int p1=0;
int p2=0;
int count = 0;//重复的数的个数
//初始下标p1与p2均为0
//下标p1遍历整个旧数组，下标p2指向新数组
while(p1 < numsSize){
if(nums[p1] != val){
nums[p2++] = nums[p1++];
}
else{
++p1;
++ccount;
}
}
return numsSize - count;
}2. 移除元素
2.1 题目链接
力扣（LeetCode）链接：删除有序数组中的重复项
2.2 题目要求
一个 升序排列 的数组
，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。 由于在某些语言中不能改变数组的长度，所以必须将结果放在数组
的第一部分。更规范地说，如果在删除重复项之后有
个元素，那么
的前
个元素应该保存最终结果。 将最终结果插入
的前
个位置后返回
。 不要使用额外的空间，你必须在 原地 修改输入数组 并在使用
额外空间的条件下完成。 判题标准:
//系统会用下面的代码来测试你的题解:
int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案
int k = removeDuplicates(nums); // 调用
assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
assert nums[i] == expectedNums[i];
}如果所有断言都通过，那么您的题解将被 通过。
示例 1： 输入：
输出：
解释：函数应该返回新的长度
， 并且原数组
的前五个元素被修改为
。不需要考虑数组中超出新长度后面的元素。 提示：
已按 升序 排列
2.3 代码框架
int removeDuplicates(int* nums, int numsSize){
}2.4 思路分析
题目要求对有序数组进行去重处理，并且不开辟额外的临时数组，那么思路是把题目所给的数组
当作去重后的新数组即可。
使用变量
记录原数组的下标，使用变量
记录新数组的下标,使用变量
记录重复元素的个数；
原数组中第一个元素我们默认直接放入了新数组的第一个位置，所以我们直接把
初始化为1，记录原数组可能存在的第二个元素的下标，
初始化为0，记录当前新数组的最后一个元素。
当
小于
时，进行判断： 如果
对应元素不等于
对应元素，则
先记录新数组下一个位置的下标再把
位置元素移动到
位置，更新
为原数组下一个位置的下标。 如果
对应元素等于
对应元素，说明新数组中已经存在该元素，故跳过该元素，
记录原数组数组下一个位置的下标，
不变，
自增
。
当
等于
时说明去重完毕；
时间复杂度
空间复杂度
2.5 代码实现
int removeDuplicates(int* nums, int numsSize){
int old = 1;
int new = 0;
int count = 0;
while(old < numsSize){
if(nums[old] == nums[new]){
++old;
++count;
}
else{
nums[++new] = nums[old++];
}
}
return numsSize - count;
}3. 移除元素
3.1 题目链接
力扣（LeetCode）链接：合并两个有序数组
3.2 题目要求
给你两个按 非递减顺序 排列的整数数组
和
，另有两个整数
和
，分别表示
和
中的元素数目。 请你 合并
到
中，使合并后的数组同样按 非递减顺序 排列。 注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
示例 1： 输入：
输出：
解释：需要合并
和
。 合并结果是
，其中斜体加粗标注的为
中的元素。 示例 2： 输入：
输出：
解释：需要合并
和
。 合并结果是
。 示例 3： 输入：
输出：
解释：需要合并的数组是
和
。 合并结果是
。 注意，因为
，所以
中没有元素。
中仅存的
仅仅是为了确保合并结果可以顺利存放到
中。 提示：
进阶：你可以设计实现一个时间复杂度为
的算法解决此问题吗？
3.3 代码框架
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
}3.4 思路分析
采用归并排序的思想，对两个数组元素依次进行比较，但是因为比较后的结果要存入第一个数组
,并且不借助临时数组存放结果，所以我们对这两个数组的比较不能从前往后进行，这样可能会把
中未排序的数给覆盖掉；应该从后往前倒着对两个数组进行归并排序。
整型变量
、
分别记录原数组
、
的下标；
记录新数组的下标，实际上其也是记录数组
，称呼为新旧数组只是为了好区分而已。
当
大于等于
并且
大于等于
，说明可以进行两个数组可以进行比较： 找出
对应原数组元素与
对应原数组元素的较大者，将其移动到
对应新数组位置，之后更新对应原数组下标变量
或
，更新新数组下标变量
。
当
小于
或者
小于
，说明至少有一个数组的元素已经全部移动到了新数组； 如果是原数组
元素没有全部移动到新数组，就把
中剩余元素移动到新数组； 如果是原数组
元素没有全部移动到新数组，就什么也不用做，因为新数组中的元素实际上是直接存入了原数组
中，当原数组
全部元素移动完成就可以看成已经结束了。
时间复杂度
空间复杂度
3.5 代码实现
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
int old1 = m-1;//旧数组1的下标old1
int old2 = n-1;//旧数组2的下标old2
int new = nums1Size-1;//新数组1的下标
//归并排序思想，但不能从前往后开始排序，而要反过来从后往前排序。因为会覆盖未排序元素。
//当有一个数组的下标小于0，说明某一个旧数组元素已经全部移动到新数组了，结束循环
while(old1 >= 0 && old2 >= 0){
if(nums1[old1] > nums2[old2]){
nums1[new] = nums1[old1];
--old1;
--new;
}
else{
nums1[new] = nums2[old2];
--old2;
--new;
}
}
//因为新数组就是旧数组1，只需旧数组2的全部元素移动到新数组就完成了，即只考虑old2
while(old2 >= 0){
nums1[new] = nums2[old2];
--new;
--old2;
}
}结语
本文到这里就结束了，如果有错误之处欢迎批评指正！