顺序表oj
话不多说，上题⛹️♂️🏀
一.移除元素
链接: 27.移除元素
题目描述：
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1：
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
示例 2：
输入：nums = [0,1,2,2,3,0,4,2], val = 2 输出：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0,
4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
思路一：
1.遍历整个数组，找出数组中值为val的位置pos
2.将pos位置后的值往前移动，覆盖pos位置的val
3.再次循环，重复1，2步，至数组中无val值
实现：
int removeElement(int* nums, int numsSize, int val){ int pos=0; while(1) { //遍历整个数组，找出数组中值为val的位置pos for(;pos<numsSize;pos++) { if(nums[pos]==val) { break; } } //判断循环结束的条件 if(pos==numsSize) { break; } //删除元素 int i=pos+1; for(;i<numsSize;i++) { nums[i-1]=nums[i]; } numsSize--; } return numsSize;
此方法时间复杂度为o（n^2）,时间复杂度太高，还可以进行优化。
思路2：
1.创建一个等长数组tmp
2.将原数组遍历，如果值不为val就放入新数组
最后将tmp拷贝回原数组
实现：
int removeElement(int* nums, int numsSize, int val){ // 1. 申请numSize个元素的新空间 int* temp = (int*)malloc(sizeof(int)*numsSize); if(NULL == temp) { return 0; } // 2. 将nums中非value的元素搬移到temp中 int count = 0; for(int i = 0; i < numsSize; ++i) { if(nums[i] != val) { temp[count] = nums[i]; ++count; } } // 3. 将temp中删除val之后的所有元素拷贝到nums中 memcpy(nums, temp, sizeof(int)*count); free(temp); return count; }
注意题目要求是在原数组上进行改动，那其实还可以再小小的优化一下，看思路三 ⬇。
思路三：
思路三和思路二的思想没有太大差异
代码实现：
int removeElement(int* nums, int numsSize, int val){ int i=0; int j=0; for(;i<numsSize;i++) { //如果相等，什么也不做 if(nums[i]==val) { ; } //如果不等进行赋值 //i-j=数组中值为val的个数 else { nums[j]=nums[i]; j++; } } return j; }
二.删除重复项
链接: 26.删除重复项
题目描述：
给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。
将最终结果不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例 1：
输入：插入 nums 的前 k 个位置后返回 k 。nums = [1,1,2] 输出：2, nums = [1,2,_] 解释：函数应该返回新的长度 2 ，并且原数组 nums
的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
示例 2：
输入：nums = [0,0,1,1,1,2,2,3,3,4] 输出：5, nums = [0,1,2,3,4] 解释：函数应该返回新的长度
5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
思路一：
1.由题可知，为升序数组，直接遍历数组
2.若有重复必是相连的元素
3.删除后一个元素
int removeDuplicates(int* nums, int numsSize){ int i=1; for(;i<numsSize;i++) { if(nums[i-1]==nums[i]) { int j=i+1; for(;j<numsSize;j++) { nums[j-1]=nums[j]; } numsSize--; i--;//删除后，下标都向前挪动了一位，为使所有元素全部被检查，i也得减一位 } } return numsSize; }
思路二：
- 设置一个计数，记录从前往后遍历时遇到的不同元素的个数
由于不同的元素需要往前搬移，那count-1就是前面不同元素
搬移之后，最后一个元素的位置，下一次在遇到不同元素就应该
搬移到count位置
2. 遍历数组，如果nums[i]与nums[count-1]不等，就将nums[i]搬移
到nums[count]位置，不同元素多了一个，给count++
3. 循环结束后，返回count
int removeDuplicates(int* nums, int numsSize){ int count = 0; for(int i = 1; i < numsSize; ++i) { if(nums[i] != nums[count]) nums[++count] = nums[i]; } ++count; return count; }
思路三
快慢指针法（双指针法）
遍历数组
如果相等，慢指针不动，快指针往前移
不等，将快指针所指向的值赋值给慢指针，慢指针往前移，快指针往前移
int removeDuplicates(int* nums, int numsSize){ if(numsSize==1) { return 1; } int fast=1; int slow=1; while(fast<numsSize) { //如果相等，满指针不动，快指针往前移 //不等，将快指针所指向的值赋值给慢指针，慢指针往前移，快指针往前移 if(nums[fast]!=nums[fast-1]) { nums[slow]=nums[fast]; slow++; } fast++; } return slow; }
三.合并两个有序数组
链接: 88.合并有序数组
题目描述：
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
示例 1：
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6] 解释：需要合并 [1,2,3] 和 [2,5,6] 。 合并结果是 [1,2,2,3,5,6]
，其中斜体加粗标注的为 nums1 中的元素。
示例 2：
输入：nums1 = [1], m = 1, nums2 = [], n = 0 输出：[1] 解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。
示例 3：
输入：nums1 = [0], m = 0, nums2 = [1], n = 1 输出：[1] 解释：需要合并的数组是 [] 和 [1]
。 合并结果是 [1] 。 注意，因为m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0
仅仅是为了确保合并结果可以顺利存放到 nums1 中。
思路：
1.遍历两数组，将nums1和nums2中元素进行对比
2.将较大的元素放入nums1中的末尾
3.必有一个数组的元素没有遍历完，如果是nums1中的元素，无需处理，如果为nusm2中的元素，还需再次遍历将剩余的元素放入nums1中
实现：
在这里插入代码片void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){ if(n==0&&m==0) { return; } int n1=m-1; int n2=n-1; int n3=nums1Size-1; while(n1>=0&&n2>=0) { if(nums1[n1]>=nums2[n2]) { nums1[n3--] =nums1[n1--]; } else { nums1[n3--]=nums2[n2--]; } } if(n2<0) { ; } if(n1<0) { for(int i=0;i<=n2;i++) { nums1[i]=nums2[i]; } } }
其实此题还有其它方法如双指针法，但在此题中两种方法实现思路大致一致，只在代码上略微有点区别，故不多介绍有兴趣的兄弟可以自己下去实现一下。
望对诸位佬有点帮助
