如何在不使用另一个数组的情况下从数组中删除重复项?

How can I remove duplicates from array without using another array?

我在面试中发现了这个问题

我有数组

a = [0,0,1,1,1,2,2,3,4]

我有一个已排序的数组,我想从给定数组 中删除重复项而不使用任何其他数组 ,即 space 复杂度应为 O(1) .输出应该是没有重复的数组的长度。

输出,

a = [0,1,2,3,4]
length = 5

这种方法一点也不省时,但它符合您的 space 标准:

>>> a = [0,0,1,1,1,2,2,3,4]
>>> while any(a.count(x) > 1 for x in a):
...     for x in a:
...         if a.count(x) > 1:
...             x = a.pop(x)
...             break
...
>>> a
[0, 1, 2, 3, 4]

通常推荐的做法当然是:

a = list(set(a))
def duplicate_remover(input_array):
    for item in input_array:
        while input_array.count(item) > 1:
            input_array.remove(item)
    return input_array

my_array = [0,0,0,0,0,1,1,2,2,2,3,3,3,4,5,6]
print(duplicate_remover(my_array))

如果你真的想要这个常量space,你需要小心不要做任何会重新分配新数组或临时数组的事情。您可以通过简单地覆盖数组前面的元素并跟踪计数来做到这一点。最后,解决方案将是从 0count 的数组的前切片:

a = [0,0,1,1,1,2,2,3,4]

current = None
count = 0

for n in a:
    if n != current:
        a[count] = n
        count+=1
        current = n

a[:count]  
# [0, 1, 2, 3, 4]

这将是线性时间和常数 space。