【Leedcode】顺序表必备的三道面试题（附图解）

顺序表必备的三道面试题（附图解）

---

---

前言

本文给大家介绍三道顺序表学习过程中Leedcode上的OJ题！附源码和图解！

---

一、第一题

1.题目

题目如下（示例）：

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。//接口型
int removeElement(int* nums, int numsSize, int val)
{
}

---

2.思路+图解

思路一：通过遍历找到所有的val，一次挪动数据覆盖删除(时间复杂度O(N^2)),不符合题意。

---

能否将时间复杂度变成 O(N) 呢?
思路2：一次遍历nums数组，把不是val的值，放到tmp数组，再把tmp数组的值拷贝回去。如下图！

这样处理的时间复杂度为O(2N)->O(N)，空间复杂度O(N) （以空间换时间）

---

能否将空间复杂度优化到 O(1) 呢？
思路3：请看图解！

---

3.源码

代码如下（示例）：

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

---

二、第二题

1.题目

代码如下（示例）：

一个升序排列的数组nums,请你原地删除重复出现的元素,使每个元素只出现一次,
返回删除后数组的新长度,元素的 相对顺序应该保持一致由于在某些语言中不能改变数组的长度,所以必须将结果放在数组nums的第一部分.
更规范地说，如果在删除重复项之后有k个元素，那么nums的前k个元素应该保存最终结果。将最终结果插入nums的前k个位置后返回k不要使用额外的空间，你必须在原地修改输入数组并在使用O(1)额外空间的条件下完成。int removeDuplicates(int* nums, int numsSize)//接口型
{
}

---

2.思路+图解

思路一：挪动数据，如果有重复的元素，就把重复后的元素前挪一步（时间复杂度:O(N^2)),不符合题意

---

思路二：再开辟一个数组，如果重复的元素跳过去，把没重复的元素移到新数组里
这样处理的时间复杂度为O(2N)->O(N)，空间复杂度O(N) （以空间换时间），不符合题意

---

思路三：如下图解释！

---

3.源码

代码如下（示例）：

int removeDuplicates(int* nums, int numsSize)
{int i=0;int j=1;int dst=0;if(numsSize==0){return;}while(j<numsSize){if(nums[i]==nums[j]){++j;}else{nums[dst]=nums[i];++dst;i=j;j++;}}nums[dst]=nums[i];dst++;return dst;
}

---

三、第三题

1.题目

题目如下（示例）：

给你两个按非递减顺序排列的整数数组nums1和nums2，另有两个整数m和n，分别表示nums1和nums2中的元素目。请你 合并nums2到nums1中，使合并后的数组同样按非递减顺序排列。注意：最终，合并后数组不应由函数返回，而是存储在数组nums1中。为了应对这种情况，
nums1的初始长度为m + n，其中前m个元素表示应合并的元素，后n个元素为0，应忽略。nums2的长度为n。void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
}

2.思路+图解

这里就直接讲最终的思路和解法！如下图图解所示！

---

---

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--];}else{nums1[end--]=nums2[end2--];}}while(end2>=0){nums1[end--]=nums2[end2--];}
}

---

总结

以上就是今天要讲的内容，本文介绍了学习顺序表中的三道面试题以及图解+源代码
如果我的博客对你有所帮助记得三连支持一下，感谢大家的支持！