算法笔记_面试题_3.去除数组中的重复元素

题目

26. 删除排序数组中的重复项

难度：简单

给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

示例 1:

给定数组 nums = [1,1,2], 

函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1，2
你不需要考虑数组中超出新长度后面的元素。

示例 2:

给定 nums = [0,0,1,1,1,2,2,3,3,4],

函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0，1,2,3,4,
你不需要考虑数组中超出新长度后面的元素。

最优代码之一

动画演示：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/solution/shi-ping-dong-hua-jie-xi-bao-ni-dong-by-novice2mas/

思路解析：定义两个索引 i 和 j 。i遍历数组使用，j指向重复待替换元素。 i和j都从0开始，当第i个元素与第j个元素相等时，什么都不做，当不相等时，j=j+1先向前走一位，指向待替换元素，此时再使用第i个元素进行替换。

#include 
#include 
#include 

int removeDuplicates(std::vector& nums)
{
	int j = 0;
	if (nums.size() == 0) return 0;
	for (int i = 0; i < nums.size(); ++i)
	{
		if (nums[j] != nums[i])
		{
			nums[++j] = nums[i];
		}
	}
	nums.resize(j+1); // j是指向最后一个元素的索引值（即从0开始的），所以长度是j+1
	return j+1;
}

int main(int argc, char* argv[])
{
	std::vector ver = { 0,0,1,1,1,2,2,3,3,4 };
	removeDuplicates(ver);
	for (int i = 0; i < ver.size(); ++i)
	{
		std::cout