题目描述
在有序数组中删除重复元素，使每个数字出现且只出现1次，并返回数组的新的长度。要求：不允许申请额外空间，即要求恒定的空间复杂度。
我的解法——记录应该前移的位数
- **最好的方法！！ **
- 用一个额外空间记录当前元素应该向前移的位数，这个数now随着数组往后遍历不断变化：
- 若当前元素和之前元素相等：now++
- 若当前元素和之前元素不等：now不变
- n的复杂度。
- 结果：beat 44.82%
class Solution(object):
def removeDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
now = 0
for i in range(1,len(nums)):
if(nums[i] == nums[i - 1]):
now += 1
nums[i - now] = nums[i]
return len(nums) - now
其他解法——双指针
- 采用两个指针l和r，l记录不重复元素的位置，r从l的下一个开始遍历数组，如果r位置的数字等于l位置的数字，说明该数字重复出现，不予处理；如果r位置的数字不等于l位置的数字，说明该数字没有重复，需要放到l的下一位置，并使l加1。然后用Sum Two的算法搞定。
- 一层循环，n的复杂度
class Solution
{
public:
int removeDuplicates(int A[], int n)
{
if(n == 0)
return 0;
int l = 0;
for(int r = 1; r < n; ++ r)
if(A[r] != A[l])
A[++ l] = A[r];
return l + 1;
}
};
参考答案
https://leetcode.com/problems/remove-duplicates-from-sorted-array/solution/