26.删除排序数组中的重复项 Remove Duplicates from Sorted Array
题解双指针算法流程：复杂度分析PythonJava(待完成)
题解
本题难点，原地修改 且在
O
(
1
)
O(1)
O(1)空间下完成
双指针
算法流程：
空数组返回0定义指针
i
i
i从第二个元素开始遍历，对于
n
u
m
s
[
j
]
nums[j]
nums[j]:
判断条件
n
u
m
s
[
j
]
!
=
n
u
m
s
[
i
]
nums[j]!=nums[i]
nums[j]!=nums[i]，说明
n
u
m
s
[
j
]
nums[j]
nums[j]为
n
u
m
s
[
i
]
nums[i]
nums[i]的下一个不相同元素，此时令
i
+
1
i+1
i+1。互换
n
u
m
s
[
j
]
nums[j]
nums[j]和
n
u
m
s
[
i
]
nums[i]
nums[i],此时对应两种情况：
满足条件
n
u
m
s
[
j
]
!
=
n
u
m
s
[
i
]
nums[j]!=nums[i]
nums[j]!=nums[i]，则
i
=
i
+
1
i=i+1
i=i+1,表示将
n
u
m
s
[
j
]
nums[j]
nums[j]放到下个位置不满足条件
n
u
m
s
[
j
]
!
=
n
u
m
s
[
i
]
nums[j]!=nums[i]
nums[j]!=nums[i]，说明
n
u
m
s
[
j
]
nums[j]
nums[j]依旧为重复元素，替换到
i
i
i处，不会影响结果 返回长度
i
+
1
i+1
i+1
复杂度分析
时间复杂度：
O
(
n
)
O\left(n\right)
O(n),只扫描了一遍空间复杂度：
O
(
1
)
O(1)
O(1)
Python
class Solution:
def removeDuplicates(self
, nums
: List
[int]) -> int:
n
=len(nums
)
if(n
<=1):
return n
i
=0
for j
in range(1,n
):
if(nums
[i
]!=nums
[j
]):
i
+=1
nums
[i
]=nums
[j
]
return i
+1
Java(待完成)
