LeetCode_26: Remove Duplicates from Sorted Array - LeetCode

# 引言

题目链接：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
	}

LeetCode