LeetCode 26. Remove Duplicates from Sorted Array

题目

Given a sorted array, 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 in place with constant memory.

For example,
Given input array 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 new length.

分析

  • 输入:一个有序数组
  • 任务:去重
  • 条件:不申请新数组,对原数组原地操作,常数内存
  • 输出:去重后数组长度

代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
# @param a list of integers
# @return an integer
def removeDuplicates(self, nums):
if not nums:
return 0
new_tail = 0
for i in range(1, len(nums)):
if nums[i] != nums[new_tail]:
new_tail += 1
nums[new_tail] = nums[i]
return new_tail + 1

解释

遍历数组,用一个游标 new_tail 记录去重后数组最后一个数的下标,每次遍历时,比较当前值和 new_tail 处的值,如果相等,直接遍历下一个值,如果不相等,把当前值移到 new_tail 后,new_tail +1,继续下一次遍历