# 引言

题目链接: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
}
更新于 阅读次数