题目地址:https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/
题目:
给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。
不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
示例 1:
给定数组 nums = [1,1,2],
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
你不需要考虑数组中超出新长度后面的元素。
试题分析:
这道题是一道典型的有序数组操作题,要抓住三个要点,一个是有序数组,另一个是原地删除,还有一个是不考虑超出新长度后面的元素。
有序数组意味着通过O(n)的时间复杂度,只需要循环一次就能够剔除重复数字,要利用好有序这个特点,当有连续相等的数字时要做跳过处理。
原地删除不使用额外空间,这就要求充分利用会被删除的重复数字的位置。
综上考虑下来,可以使用快慢双指针方案来解该题,慢指针指向数组当前循环过程中最后一个不重复的数值,快指针指向当前循环体正在处理的数值。当比较两个指针的时候这就会有两种情况发生,当慢指针和快指针指向的值相等的时候说明快指针指向了重复的值,这时候慢指针不移动,只对快指针进行向后移动;当快指针和慢指针指向的数值不等的时候,说明这个数字是要加到新数组里的,这时候将慢指针后移动一位,用快指针指向的值赋给慢指针后移后指向的值,这时你可能会说直接覆盖慢指针后的值不就造成数据被覆盖了?答案是不会,自己思考下,慢指针后面的数据会有两种情况,一种是和慢指针指向的值相等的重复数字,还有一种是和慢指针不相等的数字,如果慢指针是有连续重复值则用快指针指向的不相等的值进行覆盖重复值位置,如果慢指针和快指针之间没有重复的可覆盖空间慢快指针指向的是两个不相等的数字,则在慢指针后移一位后,其实相当于快指针将值赋值给了自己,这点非常巧妙,需要自己好好体会。
public int removeDuplicates(int[] nums) {
if(nums.length == 0){
return 0;
}
//i代表慢指针
int i = 0;
//j代表快指针
int j = 1;
for(;j<nums.length;j++){
if(nums[i] != nums[j]){
//慢指针指向的数字和快指针不相等的话则慢指针向后移动一位
i++;
//将快指针指向的值赋值给慢指针指向的值,
// 1)如果数组内的值是连续不相等,则此时i=j快慢指针都指向同一个数值,相当于原地赋值
// 2)如果连续相等后的第一个不相等,则将i++后j指向的第一个不相等的值赋值给i指向的值
nums[i] = nums[j];
}
}
//i是下标值需要加1才是length
i++;
return i;
}
源码路径:com.monkey01.array.RemoveDuplicateFromSortedArray_26
配套测试代码路径:test目录com.monkey01.array.RemoveDuplicateFromSortedArray_26Test