LeetCode_26: Remove Duplicates from Sorted Array

# 引言

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