题目描述:
给你一个 升序排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
由于在某些语言中不能改变数组的长度,所以必须将结果放在数组nums的第一部分。更规范地说,如果在删除重复项之后有 k 个元素,那么 nums 的前 k 个元素应该保存最终结果。
将最终结果插入 nums 的前 k 个位置后返回 k 。
不要使用额外的空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例一:
示例二:
思路分析:
这道题目的要求是:对于给定的有序数组
n
u
m
s
nums
nums删除重复元素,在删除元素之后,每个元素只出现一次,并返回新的长度,上述操作必须通过原地修改数组的方法,使用
O
(
1
)
O(1)
O(1)的空间复杂度完成。
由于给定的数组
n
u
m
s
nums
nums是有序的,因此对于任意
i
<
j
i<j
i<j,如果
n
u
m
s
[
i
]
=
n
u
m
s
[
j
]
nums[i]=nums[j]
nums[i]=nums[j],则对任意的
i
⩽
k
⩽
j
i\leqslant k\leqslant j
i⩽k⩽j,必有
n
u
m
s
[
i
]
=
n
u
m
s
[
k
]
=
n
u
m
s
[
j
]
nums[i]=nums[k]=nums[j]
nums[i]=nums[k]=nums[j],即相等的元素在数组中的小标一定是连续的。利用数组有序的特点,可以通过双指针的方法删除重复元素。
如果数组
n
u
m
s
nums
nums的长度为0,则数组不包含任何元素,因此返回0;
当数组
n
u
m
s
nums
nums的长度大于0,数组中至少包含一个元素,在删除元素之后也至少剩余一个元素,因此
n
u
m
s
[
0
]
nums[0]
nums[0]保持原状即可,从下标1开始删除重复元素。
定义两个指针
f
a
s
t
fast
fast和
s
l
o
w
slow
slow分别为快指针和慢指针,快指针表示遍历数组到达的下标位置,慢指针表示下一个不同元素要填入的下标位置,初始时两个指针都指向下标1;
假设数组
n
u
m
s
nums
nums的长度为
n
n
n,将快指针
f
a
s
t
fast
fast依次遍历从1到
n
−
1
n-1
n−1的每个位置。对于每个位置,如果
n
u
m
s
[
f
a
s
t
]
≠
n
u
m
s
[
f
a
s
t
−
1
]
nums[fast]\neq nums[fast-1]
nums[fast]=nums[fast−1]说明
n
u
m
s
[
f
a
s
t
]
nums[fast]
nums[fast]和之前的元素都不同,因此将
n
u
m
s
[
f
a
s
t
]
nums[fast]
nums[fast]的值复制到
n
u
m
s
[
s
o
l
w
]
nums[solw]
nums[solw],然后将solw的值加1,即指向下一个位置。
遍历结束之后,从
n
u
m
s
[
0
]
nums[0]
nums[0]到
n
u
m
s
[
s
o
l
w
−
1
]
nums[solw-1]
nums[solw−1]的每个元素都不相同且包含原数组中的每个不同的元素,因此新的长度为solw,返回slow即可。
代码展示:
class Solution { public int removeDuplicates(int[] nums) { int n=nums.length; if(nums.length==0){ return 0; } int solw=1; for(int fast=1;fast<n;fast++){ if(nums[fast]!=nums[fast-1]){ nums[solw++]=nums[fast]; } } return solw; } }