LeetCode_35 Remove Duplicates from Sorted Array

题目描述:

1
2
3
Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory

输入样例:

1
2
3
4
5
Example 1:
Given nums = [1,1,2],
Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.
It doesn't matter what you leave beyond the returned length.

1
2
3
4
5
Example 2:
Given nums = [0,0,1,1,1,2,2,3,3,4],
Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.
It doesn't matter what values are set beyond the returned length.

思路和code
这道题的题意非常地费解,简单理解为数组去重,但是要求只对原数组去重,给入的是nums,去重后的也必须是这个nums,也就是说指针必须不变。因此,重新开辟新的数组来寸去重后的数,最后虽然返回的值一样,但是会报错,因为不是之前的那个nums了。

1
2
3
4
5
6
7
8
# 错误的做法
def removeDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
return len(set(nums)) #set是比较好用的去重函数,但是内部实现过程不是删除nums中的重复数,
#而是新开的一个数组来存,返回新开的数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 正确的做法
def removeDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums or len(nums) == 0:
return 0
if len(nums) == 1:
return len(nums)
num_len, i = len(nums) - 1, 0
while i < num_len - 1:
if(nums[i] == nums[i + 1]):
nums.pop(i + 1)
num_len -= 1
else:
i += 1
if nums[-1] == nums[-2]:
nums.pop(-1)
return len(nums)