不使用额外内存时在有序列表中去重

Question: 不使用额外内存时在有序列表中去重

👉LeetCode链接👈

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.

给定一个有序数组，删除重复的元素，保证每个元素只出现一次，并且返回新的数组长度

注意！ 注意！ 注意！

问题没有这么简单，不允许给另外一个列表使用额外的内存空间，只能在常量内存中操作

Example

1
2
3
Given input array nums = [1,1,2],

Your function should return length = 2,

Answer

1
2
3
4
5
6
7
8
9
10
def removeDuplicates(A):
    if not A:
        return 0
    new_tail = 0
    for i in range(1, len(A)):
        print(A)
        if A[i] != A[new_tail]:
            new_tail += 1
            A[new_tail] = A[i]
    return new_tail + 1

Thinking

先定义一个新的索引，值为 0， new_tail 用来存储当前最后一个不重复的数字是多少，并且这个索引页代表了有多少个不重复的数字了。从索引为 1 的位置，也就是第二个元素开始，与 new_tail 位置的元素比较相同的话，不做任何操作，继续向下取下一个值，不同的话，将 new_tail 这个索引加一，将最新的不重复的数字存入到新的 new_tail 的位置上，然后继续往下判断。所以 new_tail 位置上的数据，始终是与 [0:new_tail] 之间的数据不重复的数据并且也是循环到最新的位置时，遇到的最后一个不重复的数据由于 new_tail 初始值是 0，所以 new_tail + 1 也就是当前所有不重复数据的总和

Why

刚开始想得太简单了，寻思着直接返回 len(set(A)) 不就是返回去重后的长度了么。可是在 set 的 __init__ 方法中发现了这么一句话 set() -> new empty set object 才知道使用set方法时是创建了一个新的 set object 也就意味着使用了新的内存空间