Leetcode—移除元素、删除有序数组中的重复项、合并两个有序数组

移除元素

此题简单，用双指针方法即可，
如果右指针指向的元素不等于val，它一定是输出数组的一个元素，我们就将右指针指向的元素复制到左指针位置，然后将左右指针同时右移；
如果右指针指向的元素等于 val，它不能在输出数组里，此时左指针不动，右指针右移一位。

且最后需要输出的数组长度就是left的值。不多说，上代码：

int removeElement(int* nums, int numsSize, int val)
{int left =0;int right =0;for(int i =0;i<numsSize;i++){if(nums[right] != val){nums[left]=nums[right];++left;++right;}else{++right;}}return left;}

时间复杂度：O(N)
空间复杂度：O(1)

删除有序数组中的重复项

暴力想法

（注意是暴力想法，不是暴力解法！）
作为直男直接就是想实现。
直接遍历，看题目是已经确定了是有序的，遇到与上一个不相等的直接给他拿到新的数组里面存起来。遍历完直接新数组就是答案。
看样子是很接近了哈！毕竟属于简单的题目。但是， O(1) 额外空间的条件下完成这个是我们跨不过去的坎。既然如此那就得考虑在原数组上操作。

双指针法

定义两个指针fast 和 slow 分别为快指针和慢指针，快指针表示遍历数组到达的下标位置，慢指针表示下一个不同元素要填入的下标位置，初始时两个指针都指向下标 1。
假设数组nums 的长度为 n。将快指针 fast 依次遍历从 1 到 n-1 的每个位置，对于每个位置，如果nums[fast] !=nums[fast-1],说明 nums[fast] 和之前的元素都不同，因此将 nums[fast] 的值复制到nums[slow]，然后将 slow 的值加 1，即指向下一个位置。遍历结束之后，从 nums[0] 到 nums[slow−1] 的每个元素都不相同且包含原数组中的每个不同的元素，因此新的长度即为 slow，返回 slow 即可。

//C
int removeDuplicates(int* nums, int numsSize)
{int right =1;int left =1;for(int i=1;i<numsSize;i++){if(nums[right-1]!=nums[right]){nums[left]=nums[right];++left;++right;}else{++right;}}return left;
}

合并两个有序数组

方法一：直接合并后排序

最直观的方法是先将数组 nums 2放进数组nums 1的尾部，然后直接对整个数组进行排序。

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, nums1Size, sizeof(int), cmp);
}

时间复杂度：O((m+n)\log(m+n))
空间复杂度：O(log(m+n))

方法二：逆向双指针

观察可知，nums 1 的后半部分是空的，可以直接覆盖而不会影响结果。因此可以指针设置为从后向前遍历，每次取两者之中的较大者放进 nums 1的最后面。

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--];}}

时间复杂度：O(m+n)
空间复杂度：O(1)