删除数组中的重复项
给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 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。你不需要考虑数组中超出新长度后面的元素。复制代码
说明:
为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以**“引用”**方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝int len = removeDuplicates(nums);// 在函数里修改输入数组对于调用者是可见的。// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。for (int i = 0; i < len; i++) { print(nums[i]);}复制代码 思路
关键点
- 排序数据
- 不要使用额外的数组空间
- 原地删除重复出现的元素
解决问题
-
将数组中的第一位置数
nums[0]定义为一个校验位int cur = nums[0], 从索引为1处，对数组进行循环 -
将校验位
cur依次与数组中每一个索引位置的值进行比较
第一次比较 两个值相等，不做改变
第二次比较 nums[2] != cur
这时需要替换元素位置，将cur替换为nums[2], 这时需要申明一个 int curIndex = 1; 变量，记录现在数组中存在的不重复数据的索引的位置， 初始值为 1, 同时将nums[2]的值赋值给nums[curIndex]
上图中红色虚线框内便已经是不重复的数据
紧接着同时将index, 与 curIndex 向后移动一位, 接着循环,此时标志位cur 已经变成了2
第三次循环比较
标志位 cur 与 nums[3] 相等, 表明为重复元素, nums[3] 中元素已经在红色虚线框中出现过
将index 向后移动一位, curIndex 保持不变, 红色虚线框中的内容保持不变, cur 标识位保持不变
第四次循环比较
此时, 标志位和nums[4]不相等, 就跟步骤二一样,需要替换到 nums[curIndex] 与cur 位置处的元素
此时同时将index 与 curIndex 向后移动一位
第五次循环比较
标志位 cur 与 nums[5] 相等, 表明为重复元素, nums[5] 中元素已经在红色虚线框中出现过
将index 向后移动一位, curIndex 保持不变, 红色虚线框中的内容保持不变, cur 标识位保持不变
第六次循环比较
不相等, 替换 curIndex 处的元素
并向后移动 curIndex = curIndex + 1
最后curIndex 处的位置便是题目的解
代码
class Solution { public int removeDuplicates(int[] nums) { if(nums.length == 0) { return 0; } int cur = nums[0]; int index = 1; for (int i = 1; i < nums.length ; i ++) { if(cur != nums[i]){ nums[index ++] = nums[i]; cur = nums[i]; } } return index; }}复制代码