描述：
给你一个升序排列的数组nums ，请你原地删除重复出现的元素，使每个元素只出现一次 ，返回删除后数组的新长度。元素的相对顺序应该保持一致 。
不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例1
输入：
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 。不需要考虑数组中超出新长度后面的元素。
思路一：
int removeDuplicates(int* nums, int numsSize){ if (numsSize == 0) return 0; int i = 0, j = 1; int dst = 0; 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; }
思路二：
int removeDuplicates(int* nums, int numsSize) { if (numsSize == 0) return 0; int fast = 1, slow = 1; while (fast < numsSize) { if (nums[fast] != nums[fast - 1]) { nums[slow] = nums[fast]; ++slow; } ++fast; } return slow; }
分析：时间复杂度为O(N)，空间复杂度为O(1)。
合并两个有序数组
说明：
给你两个按非递减顺序排列的整数数组nums1和nums2，另有两个整数m和n ，分别表示nums1和nums2中的元素数目。请你合并nums2到nums1中，使合并后的数组同样按非递减顺序排列。
注意：
最终，合并后数组不应由函数返回，而是存储在数组nums1中。为了应对这种情况，nums1 的初始长度为m+n，其中前m个元素表示应合并的元素，后n个元素为 0 ，应忽略。nums2 的长度为n。
示例
输入：
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] 。
进阶：
你可以设计实现一个时间复杂度为
O(m + n)的算法解决此问题吗？
思路一：
最简单直观的方法就是，先将数组nums2放进数组nums1的尾部，然后再对数组num1进行快速排序。
int cmp(int* a, int* b) { return *a - *b; } void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) { for (int i = 0; i < n; i++) { nums1[m + i] = nums2[i]; } qsort(nums1, m + n, sizeof(int), cmp); }
分析：时间复杂度：O((m+n)log(m+n))，空间复杂度：O(log(m+n)。
思路二：
开辟一个新的数组，先将小的元素存放进去。当其中一个数组的元素存放完，再将另一个数组的元素存放进去，最后将该数组的数据拷贝给目标数组。
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) { int i = 0, j = 0, k = 0; int* nums = (int*)malloc(sizeof(int) * (m + n)); //i为nums的下标，j为nums1的下标，k为nums2的下标 while (j < m && k < n) { if (nums1[j] < nums2[k]) { nums[i] = nums1[j]; i++; j++; } else { nums[i] = nums2[k]; i++; k++; } } while (j < m) { nums[i] = nums1[j]; i++; j++; } while (k < n) { nums[i] = nums2[k]; i++; k++; } memcpy(nums1, nums, sizeof(int) * (m + n)); }
分析：时间复杂度为O(m+n)，空间复杂度为O(m+n)。
思路三：
不开辟额外的空间，直接先将较大的元素存放到数组nums的后面，直到其中一个数组存放完。如果数组nums1先存放完，那么数组nums2中还有元素需要存放到数组nums1的前面；如果数组nums2先存放完，那么现在的数组num1就是所求的数组。
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) { int end = m + n - 1, end1 = m - 1, end2 = 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--]; } }
分析：时间复杂度为O(m+n)，空间复杂度为O(1)，这是这道题最优的解法。
结语
每个优秀的人都有一段沉默的时光，那段时光是付出了很多努力却得不到结果的日子，我们把它叫做扎根。
