1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if(nums.size() == 1) return 1;
int left = 0;
int right = 1;
for(int i = 1; i < nums.size(); i++){
while(nums[left] != nums[i]){
nums[right] = nums[i];
right++;
left = i;
}
}
return right;
}
};
|
双指针法，right 用于指向更新值的下标，left 用于比较是否重复。
如果nums[left] 和 nums[i]
不相等，表明遇到不是重复的新值，然后把这个新值赋值给 nums[right]，继而把
right 和 left 的下标进行更新。
二刷（2024/9/22）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if(nums.size() == 1) return 1;
int cover_index = 1;
int same_first = 0;
for(int i = 1; i < nums.size(); i++){
if(nums[same_first] != nums[i]){
nums[cover_index] = nums[i];
cover_index++;
same_first = i;
}
}
return cover_index;
}
};
|
和之前的一刷对比，我这里并没有用 while
循环，也想不起来为什么要这样做了。
实际上认真看这道题的话，我们需要三个指针：
- 一个指向接下来要用来覆盖元素的指针
- 一个是用来遍历数组的指针
- 一个用来指向第一次出现不同元素的下标
我们首先保证数组中至少两个元素，用 cover_index 初始化为
1，因为第一个下标必然不用被修改，要修改也是从下标 1
开始。至于遍历数组，用 for 循环中的 i
持续递增即可。而指向第一次出现不同元素的下标，看似需要单独用一个指针记录，也是因为这个考虑，二刷第一次的写法如上。
但你仔细想一想，非严格递增排列
的数组特性，是完全没必要单独用一个指针记录第一次出现不同元素的下标。也就有下面这种更加简洁的写法。
可这明显是思考后的成果，如果没有形成对此题的记忆也未必想到这里，就像
环形链表II
这道题，如果你记不得判断环和判断第一次交汇点的数学推理，你真吃不下。如此，我觉得优先要考虑到的是，你懂得用
cover_index 记录接下来要被覆盖的下标，这就很不错了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if(nums.size() == 1) return 1;
int cover_index = 1;
for(int i = 1; i < nums.size(); i++){
if(nums[i] != nums[i-1]){
nums[cover_index++] = nums[i];
}
}
return cover_index;
}
};
|
