1、移除元素
1.1、题目描述
1.2、思路讲解
思路一：(时间复杂度O(N^2)
如果数组元素等于val，则将后面的元素往前挪动一个位置。
思路二：(空间复杂度O(N)不符合题目要求)
用空间换时间，将不等于val的值赋值到新的数组，然后将新的数组赋值给原数组。
思路三：(时间复杂度O(N))
用双指针，一个指针(src)用来遍历数组，一个指针(dest)用来遍历有效数据，遍历一遍数组，如果该值等于val，那么src++，如果该值不等于val，将src位置的元素赋值到dest位置，然后src++，dest++，因为dest是后置++，先使用再+1，因此dest就是有效数据个数。
1.3、画图分析
下图为思路三的画图分析喔，想了解其他思路的分析私信博主喔！
1.4、代码实现
思路三
int removeElement(int* nums, int numsSize, int val) { int dest=0; int src=0; while(src<numsSize) { if(nums[src]!=val) { nums[dest++]=nums[src++]; } else { src++; } } return dest; }
此处只需返回不等于val值的个数，因此可以少去等于val的判断，代码实现如下。
int removeElement(int* nums, int numsSize, int val) { int i=0; int count=0; for(i=0;i<numsSize;i++) { if(nums[i]!=val) { nums[count]=nums[i]; count++; } } return count; }
2、删除有序数组
2.1、题目描述
2.2、思路讲解
思路一：(时间复杂度O(N^2)空间复杂度O(1))
遍历数组，如果前面一个数等于后面一个数，将后面的所有元素向前移动一个位置。但是最后一个需要特殊处理，因为最后一个位置没有元素与之相比，处理的方式就是直接将最后一个数据放入有序数组的最后一个即可。
思路二：(时间复杂度O(N)空间复杂度O(N))
用空间换时间，将前后的数据进行比较，前后不相等则放入新数组中，同样需要处理最后一个数据，处理的方式是直接将最后一个数据放入有序数组的最后一个即可。
思路三：(时间复杂度O(N)空间复杂度O(1))
使用双指针，一个指针(src)用来遍历数组，一个指针(dest)用来记录有效数据，如果前后不相等则将元素放入下标dest中，然后src++,dest++，如果相等则src++。
2.3、画图分析
思路三
2.4、代码实现
思路一
int removeDuplicates(int* nums, int numsSize) { for(int i=0;i<numsSize;i++) { for(int j=i+1;j<numsSize;j++) { if(nums[i]==nums[j]) { for(int k=j;k<numsSize-1;k++) { nums[k]=nums[k+1]; } j--; numsSize--; } } } return numsSize; }
思路三
int removeDuplicates(int* nums, int numsSize) { int dest=0; int src=0; while(src<numsSize-1) { if(nums[src]!=nums[src+1]) { nums[dest]=nums[src]; dest++; src++; } else { src++; } } nums[dest++]=nums[src];//最后一个元素的处理 return dest; }
3、合并两个有序数组
3.1、题目描述
3.2、思路讲解
思路一：(时间复杂度O(m+n)空间复杂度O(m+n)
开辟一个新的数组，大小为m+n（使用变长数组），比较两个数组的数值，哪个小则依次放入新的数组中，最后把新的数组的值赋值到nums1中。
C99标准中，新增了可变长度数组。在leetcode，牛客等刷题网站可以使用变长数组，但是VS不支持。
变长数组中的“变”不是指可以修改已创建数组的大小，一旦创建了变长数组，它的大小则保持不变。这里的“变”指的是：在创建数组时，可以使用变量指定数组的长度。(普通数组只能用常量或常量表达式指定数组的长度)
思路二：
从两个数组的末尾比较数值，大的值放入nums1的最后一个，依次类推，(前提是有序数组)。需要注意nums2是否赋值完，nums2赋值完不需要加判断，没有赋值完则需要加判断。
3.3、画图分析
思路二
3.4、代码实现
思路二
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--; } } while (end2 >= 0)//nums2还剩数值 { nums1[end] = nums2[end2]; end--; end2--; } }
总结
本篇博客就结束啦，谢谢大家的观看，如果公主少年们有好的建议可以留言喔，谢谢大家啦！
