【经典算法OJ题讲解】

1.移除元素

方法1：双指针优化
思路

如果要移除的元素恰好在数组的开头，例如序列 [1,2,3,4,5]，val 为 1时，我们需要把每一个元素都左移一位。注意到题目中说：「元素的顺序可以改变」。实际上我们可以直接将最后一个元素 5 移动到序列开头，取代元素 1，得到序列 [5,2,3,4]，同样满足题目要求。这个优化在序列中 val 元素的数量较少时非常有效。实现方面，我们依然使用双指针，两个指针初始时分别位于数组的首尾，向中间移动遍历该序列。

算法

如果左指针 left 指向的元素等于 val，此时将右指针 right 指向的元素复制到左指针 left 的位置，然后右指针 right 左移一位。如果赋值过来的元素恰好也等于 val，可以继续把右指针 right 指向的元素的值赋值过来（左指针 left 指向的等于 val 的元素的位置继续被覆盖），直到左指针指向的元素的值不等于 val 为止。

当左指针 left 和右指针 right 重合的时候，左右指针遍历完数组中所有的元素。

这样的方法两个指针在最坏的情况下合起来只遍历了数组一次。与方法一不同的是，方法二避免了需要保留的元素的重复赋值操作。

实现代码

int removeElement(int* nums, int numsSize, int val) 
{int left=0,right=numsSize;while(left<right){if(nums[left]==val){nums[left]=nums[right-1];right--;}else{left++;}}return left;
}

2.合并两个有序数组

方法1：逆向双指针 

算法

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

严格来说，在此遍历过程中的任意一个时刻，nums1 数组中有 m−p1−1 个元素被放入 nums1 的后半部，nums2数组中有 n−p2−1n个元素被放入 nums1的后半部，而在指针 p1 的后面，nums1 ​数组有 m+n−p1−1 个位置。由于 m+n−p1−1≥m−p1−1+n−p2−1 等价于 p2≥−1 永远成立，因此 p1 后面的位置永远足够容纳被插入的元素，不会产生 p1 的元素被覆盖的情况。

实现代码

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) 
{int p1 = m - 1, p2 = n - 1;int tail = m + n - 1;int cur;while (p1 >= 0 || p2 >= 0) {if (p1 == -1) {cur = nums2[p2--];} else if (p2 == -1) {cur = nums1[p1--];} else if (nums1[p1] > nums2[p2]) {cur = nums1[p1--];} else {cur = nums2[p2--];}nums1[tail--] = cur;}
}

本篇文章只介绍了题目的部分解法。如果本篇有补充的地方，欢迎私信我或在评论区指出，期待与你们共同进步。