0026. 删除有序数组中的重复项 #
- 标签:数组、双指针
- 难度:简单
题目大意 #
描述:给定一个有序数组 nums
。
要求:删除数组 nums
中的重复元素,使每个元素只出现一次。并输出去除重复元素之后数组的长度。
说明:
- 不能使用额外的数组空间,在原地修改数组,并在使用 $O(1)$ 额外空间的条件下完成。
示例:
|
|
解题思路 #
思路 1:快慢指针 #
因为数组是有序的,那么重复的元素一定会相邻。
删除重复元素,实际上就是将不重复的元素移到数组左侧。考虑使用双指针。具体算法如下:
- 定义两个快慢指针
slow
,fast
。其中slow
指向去除重复元素后的数组的末尾位置。fast
指向当前元素。 - 令
slow
在后,fast
在前。令slow = 0
,fast = 1
。 - 比较
slow
位置上元素值和fast
位置上元素值是否相等。- 如果不相等,则将
slow
后移一位,将fast
指向位置的元素复制到slow
位置上。
- 如果不相等,则将
- 将
fast
右移1
位。 - 重复上述 3 ~ 4 步,直到
fast
等于数组长度。 - 返回
slow + 1
即为新数组长度。
思路 1:代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(n)$。
- 空间复杂度:$O(1)$。