pythontip 100days-day39

题目

已知一个有序序列,请原地删除序列中重复出现的元素,返回删除重复元素后的序列长度 要求时间复杂度O(n),空间复杂度O(1)

例子

remove_duplicate([0,0,1,1,1,2,2,3,3,4,4,4,5]) -> 6
remove_duplicate([0,0,1,1,3,4,5]) -> 5

假设

1. 输入的数组不为空，且一定符合题意

tips

1. 快速排序变形

答案

解法1

def remove_duplicate(l):
    tail = 0
    for i in range(1,len(l)):
        if l[i] != l[i - 1]:
            l[tail + 1] = l[i]
            tail += 1
    return tail + 1

性能：

1. 时间复杂度O(n)
2. 空间复杂度O(1)

关键点：

1. 快速排序变形