LeetCode 26 Remove Duplicates from Sorted Array
概述
https://leetcode.com/problems/remove-duplicates-from-sorted-array/
题目要求 in place 操作，O(1) 空间复杂度。
暴力法
O(n^2) 的时间复杂度，每次遇到重复值都把后面的整体向前移动一位。
实现的时候注意移动后要手动 l --，因为 nums[l] 的值已经改变，需要重新经过循环体判断。
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int l, r;
for (l = 1, r = nums.size(); l < r; l ++) {
if (nums[l] == nums[l - 1]) {
for (int i = l; i + 1 < r; i ++) {
nums[i] = nums[i + 1];
}
r --;
l --;
}
}
return r;
}
};
TLE 了。
快慢指针法
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int s, f;
for (s = 1, f = 1; f < nums.size(); f ++) {
if (nums[f] != nums[f-1]) {
nums[s++] = nums[f];
}
}
return s;
}
};