# 引言
题目链接：https://leetcode.com/problems/remove-duplicates-from-sorted-array/
# 题目大意
给定排序的数组nums, 就地删除重复项, 使每个元素只出现一次并返回新的长度。
Hint: 不要为另一个数组分配额外的空间, 必须通过使用O(1)额外内存修改输入数组来实现此目的。
- Example
Given nums = [1,1,2],
Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.
It doesn't matter what you leave beyond the returned length.
Given nums = [0,0,1,1,1,2,2,3,3,4],
Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.
It doesn't matter what values are set beyond the returned length.# 题解
# 一句话题解
O(1)空间复杂度要求, 即利用原数组, 顺序遍历数组, 把不重复的项放在数组头部即可。维持一个index用于存储下标, 直接顺序遍历, 找到数组当前数据与前一个数据不一致即出现一个新数字, 放在当前index+1的位置即可。
# 复杂度
时间复杂度 O(n)
空间复杂度 O(1)
# AC代码
c++版本
class Solution
{
public:
int removeDuplicates(vector<int> &nums)
{
if (nums.empty())
{
return 0;
}
int ret = 1;
int index = 1;
for (int i = 1; i < nums.size(); ++i)
{
if (nums[i] != nums[i - 1])
{
++ret;
nums[index++] = nums[i];
}
}
return ret;
}
};go版本
func removeDuplicates(nums []int) int {
lens := len(nums)
if 0 == lens {
return 0
}
ret, index := 1, 1
for i := 1; i < lens; i++ {
if nums[i] != nums[i-1] {
ret++
nums[index] = nums[i]
index++
}
}
return ret
}
有什么想法，欢迎留下评论。