https://leetcode.cn/studyplan/top-interview-150/
【27】 和【28】两题是类似的
第 27 题 移除元素
第 28 题 删除有序数组中的重复项
简而言之，27 移除元素是将给定的数组中出现给定目标元素的值移除掉。
28 是一个升序——有可能不单调的数组去重。
27 的用例如 [5, 4, 4, 7, 4] 给定的查重目标数是 4，经过操作之后应当是 [5, 7]
28 的用例如 [1, 2, 3, 3, 5, 5, 6] 去重之后是 [1, 2, 3, 5, 6]
这种题目和语言有一些关系，最核心的点是一种数组移动的操作方式
当然有很多其它的办法可以解决
试举一例
对于 27 我把数组重新 copy 一边，只是在遇到给定target的时候跳过去。这样在 空间复杂度和时间复杂度都是 O(n) 的情形下解决问题
int removeElement(vector<int>& nums, int val) {
vector<int> ret;
for(int num: nums) {
if (num != val) {
ret.push_back(num);
}
}
nums.assign(ret.begin(), ret.end());
return ret.size();
}
——在内存很廉价的场景下，别人不能说什么，除非数组大到惊人的地步，用KB 或 GB衡量的时候，或者不允许修改原数组的情形，才会用这个方法，这种写法更直观
下面是更省内存的办法。
int removeElement(vector<int>& nums, int val) {
int i = 0, j = 0;
while(j < nums.size()) {
if (nums[j] == val) {
++j;
} else {
nums[i++] = nums[j++];
}
}
return i;
}
题目的本意是第二种操作
这种操作有些人成为双指针解法，其实名字听得很难受，我更想称之为条件遍历，或者数组修整。
一般的模式是
- 迭代器的移动是有条件的
- 通常迭代器不是一个，而是两个或多个
- 移动迭代器的时候，有几个状态: 分别对应迭代器移动，这需要自己定义
- 操作，达到某种状态，对应一个操作
写成代码结构就是
if (condition1) {
iter1++; //
operation1();
}
if (condition2) {
iter2++; // 有时候方向可能是相反的，iter2--
operation();
}
对题目27 而言，移动元素的条件是，当给定val 和当前遍历的元素是不是相同，而操作是复制元素的值
这道题对应两个状态，等于val 和不等于 val——等于val的时候不会发生复制操作，要忽略掉，忽略的同时移动其中一个迭代器
两个迭代器的含义，i 表示最终已经清理过的数组迭代到的当前的位置，j表示未清理的迭代位置，很明显 i <= j j总是领先 i，所以肯定是先到达数组末尾
写出的代码结构大概就是这样
if (val == num1[j]) {
// 不复制啥也不做，只移动迭代器
j++；
} else {
nums[i] = nums[j]; //复制
// 两个迭代器同时移动
i++;
j++;
}
最后形成上面那样的写法。
然后，用同样的方法看28题
28题简述为有序的数组去重的问题，因为数组有序，所以重复元素必然是连续出现的。
状态有两种
- 一种是遍历到的当前元素和已经去重过的“半成品”的最后一个相同，这时候略过不操作，只移动迭代器 j
- 一种是遍历到的当前元素和已经去重过的“半成品”的最后一个不同，那么这个元素可以加到“半成品”尾部，形成新的“半成品” 知道遍历结束
int removeDuplicates(vector<int>& nums) {
int i = 0, j = 1;
while (j < nums.size()) {
if (nums[i] == nums[j]) {
++j;
} else {
nums[i + 1] = nums[j];
++i;
++j;
}
}
return i + 1;
}
上面的代码迭代器 i 表示当前的半成品尾部的位置， j 表示当前遍历的位置——它无论如何是会移动的，当状态出现时，怎么样，另一个状态出现时又怎么样，于是可以把上面的两句相同的 ++j 简化一下，形成下面简洁的代码
int removeDuplicates(vector<int>& nums) {
int i = 0, j = 1;
while (j < nums.size()) {
if (nums[i] != nums[j]) {
nums[++i] = nums[j];
}
j++;
}
return i + 1;
}
有了上面的总结，再看一个变种题
删除有序数组中的重复项 II
简而言之就是28题变成了，删掉超过3(含3)个的重复元，只留下最多2个
也就是多了一个状态——我们梳理一下就是
- 遍历到的当前元素和前一个相同
要分两种子状态：
重复元素超过2个了 这时候不复制，移动迭代器 j，i不动
重复元素只有2个，复制，移动两个迭代器，并且修改重复状态 - 遍历到的当前元素和前一个不相同，处理和上一题一样，就是复制，两个迭代器都移动
写成了下面的程序，注释部分是我早年写的，虽然也是对的，但是逻辑是比较凌乱的，经过此番修改，变成了下面清晰的结构：我们引入一个repeat来表达当前遍历元的重复数量，初始值总是1
int removeDuplicates(vector<int>& nums) {
// int i = 0;
// int cnt = 1;
// int tail = nums.size() - 1;
// for (i = 1; i <= tail;) {
// if (nums[i] == nums[i - 1]) {
// ++cnt;
// } else if (cnt > 2) {
// for (int k = i - (cnt - 2); k <= tail - cnt + 2; ++k) {
// nums[k] = nums[k + cnt - 2];
// }
// tail = tail - cnt + 2;
// i = i - cnt + 2;
// cnt = 1;
// continue;
// } else {
// cnt = 1;
// }
// ++i;
// }
// if (cnt > 2)
// tail -= (cnt - 2);
// return tail + 1;
int i = 0, j = 1;
int repeat = 1; // 默认开始每个元素的重复次数是1 变成2才需要去重
while (j < nums.size()) {
if (nums[i] != nums[j]) {
// 这种情况直接复制 两个迭代器都移动 并且重置 repeat 的值
nums[i + 1] = nums[j];
++i;
++j;
repeat = 1;
} else {
// 分两种情况
if (repeat == 1) {
// 也复制
nums[i + 1] = nums[j];
++i;
++j;
repeat++;
} else {
// 这种情况要跳过去 移动j 不移动i 并且
++j; // repeat 可以增加也可以不管，不管的时候作为真假值处理
}
}
}
return i + 1;
}
由于有两种状态操作类似只是是否修改repeat
我们可以整理一下
让代码更紧凑一些
int removeDuplicates(vector<int>& nums) {
int i = 0, j = 1;
int repeat = 1; // 默认开始每个元素的重复次数是1 变成2才需要去重
while (j < nums.size()) {
if ((nums[i] != nums[j]) || (nums[i] == nums[j] && repeat == 1)) {
// 把需要进行相同操作的状态放在一起
if (nums[i] != nums[j]) { // 不同的地方在这里
repeat = 1;
} else {
repeat++;
}
nums[++i] = nums[j]; // 最后统一操作
}
j++; // 无论如何 j每次都是要移动的
}
return i + 1;
}
