Удалить дубликаты из массива и поддерживать порядок - O (n) время и вернуть то же значение

Question

['a', 'c','a','b','b'] -> ['a', 'c', 'b'] 

Поиск в Интернете не помог. Я не уверен, возможно ли это.

Предпочтительно написать решение в Python, но все в порядке.

=====

Edit: Я изначально сказал O (1) пространство, но я не думаю, что это возможно.

не Изменение требований:

нет пространства требования, но вы должны изменить вход на месте и вернуть его.

Answer 1

Как насчет этого? Я думаю, что временная сложность и сложность пространства равны O(n).

def unique(arr): 
    index = 0 
    s = set() 
    for i in range(len(arr)): 
     if arr[i] not in s: 
      arr[index] = arr[i] 
      index += 1 
      s.add(arr[i]) 
    arr[index:] = [] 

Answer 2

from collections import OrderedDict 

OrderedDict.fromkeys(my_array).keys() 

Answer 3

pip install oset 

import oset 

ll = oset.oset(['a', 'c','a','b','b']) 

print(ll) 

OrderedSet(['a', 'c', 'b'])` 

Answer 4

Я не думаю, что это возможно в O (N) времени и O (1) пространство. Чтобы получить время O (n), вы должны иметь блокнот (с вставкой и поиском O (1), например set), записывая все элементы, которые вы уже видели; что требует O (m) пространства (где m - количество уникальных элементов). И наоборот, для того, чтобы получить O (1) пространство, вы должны повторно ранжировать ранее элементы в массиве для каждого элемента, что является O (n).

Если вы примете блокнот O (m), это соответствует требованию «изменить массив на месте» и работает в O (n) времени.

def remove_duplicates(arr): 
    """Remove all duplicated elements from ARR in O(m) space and O(n) time. 
     ARR is modified in place and is not returned (like `sort`).""" 
    n = len(arr) 
    if n <= 1: return 
    seen = set((arr[0],)) 
    i = 1 
    j = 1 
    while i < n: 
     if arr[i] not in seen: 
      seen.add(arr[i]) 
      arr[j] = arr[i] 
      j += 1 
     i += 1 
    del arr[j:i] 

Это все равно будет О (п) время, если я удалил элементы из массива, как я итерация над ним, потому что del arr[i] сам по себе является О (п) операции: она должна скользить все после i вниз один. del arr[j:i], где i проходит мимо конца массива должен быть O (1), но если это действительно имеет значение, вам нужно будет check the implementation.

И если вы должны иметь O (1) пространство, здесь О (п) время алгоритм:

def remove_duplicates_quadratic(arr): 
    """Remove all duplicated elements from ARR in O(1) space and O(n²) time. 
     ARR is modified in place and is not returned (like `sort`).""" 
    n = len(arr) 
    i = 0 
    while i < n: 
     for j in range(i): 
      if arr[j] == arr[i]: 
       del arr[i] 
       n -= 1 
       break 
     else: 
      i += 1 

Я делаю ручную индексацию массива в них, так как удаление элементов из массива вы «Повторение с использованием любой из обычных конструкций ..in небезопасно. Вы можете использовать цикл for..in в первом, но вы потеряете parallel structure, чтобы он был менее читаемым.

В случае, если вы не видели его раньше, an else clause on a loop выполняется только в случае, если цикл не вышел через break.

Answer 5

Чтобы сохранить скорость, вам необходимо использовать пространство O (n) для записи уже существующих записей. Если имеется большое количество дубликатов, это не займет много места. Однако операция del на стандартном массиве равна O (n), поскольку она должна сдвигать все следующие элементы.

def uniquify(data): 
    used = set() 
    i = 0 
    while i < len(data): 
     if data[i] in used: 
      del data[i] # or data.pop(i) 
     else: 
      used.add(data[i]) 
      i += 1 
    return data # not strictly necessary because array is modified in-place 

Answer 6

O (п), О (п) пространство

uniqueList = [] 
index = 0 
while index < len(myList): 
    item = myList[index] 
    if item not in uniqueList: uniqueList.append(item) 
    else: myList.pop(index) 
    index += 1 

Примечание: Не изменять список вы переборе, как показано ниже:

for index, item in enumerate(myListCopy): 
    if item not in uniqueList: uniqueList.append(item) 
    else: myList.pop(index) 

O (n^2) время, O (1) пространство Оно конечно ограничено n^2, но на самом деле это меньше.

index = 0 
while index < len(myList): 
    subIndex = index + 1 
    while subIndex < len(myList): 
     if myList[subIndex] == myList[index]: myList.pop(subIndex) 
     subIndex += 1 
    index += 1 

O (п), O (1) пространство Если список отсортирован, и вы не против удаления первых дубликатов.

for item in myList: 
    if myList.count(item) > 1: myList.remove(item) 

Answer 7

lst1= ['a', 'c','a','b','b'] #-> ['a', 'c', 'b'] 
lst2 = [] 

for l in lst1: 
    if l not in lst2: 
     lst2.append(l) 
print lst2