Удаление повторяющихся символов в строке без использования рекурсии

Question

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

Моя идея состояла в том, чтобы определить целочисленный массив размером 26, где 0-й индекс будет соответствовать букве a и 25-й индекс для буквы z, и инициализировать все элементы равными 0. Таким образом, мы пройдем всю строку один раз и будем увеличивать значение по желаемому индексу по мере того, как встречаем букву.

и затем мы еще раз передвинем строку, и если значение по желаемому индексу равно 1, мы распечатаем букву, в противном случае - нет.

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

если кто-нибудь может предложить идеи лучшей эффективности, это будет очень полезно !!

Answer 1

Ваше решение определенно соответствует критериям времени O (n).Вместо массива, который был бы очень и очень большим, если разрешенный алфавит велик (Unicode имеет более миллиона символов), вы можете использовать простой хеш.Вот ваш алгоритм в (неоптимизированном) Ruby:

def undup(s) 
  seen = Hash.new(0)
  s.each_char {|c| seen[c] += 1}
  result = ""
  s.each_char {|c| result << c if seen[c] == 1}
  result
end

puts(undup "")
puts(undup "abc")
puts(undup "Olé")
puts(undup "asdasjhdfasjhdfasbfdasdfaghsfdahgsdfahgsdfhgt")

Он делает два прохода через строку, и, поскольку поиск по хешу менее линейный, вы хороши.

Вы можетескажем, Hashtable (как и ваш массив) использует постоянное пространство, хотя и большое, потому что оно ограничено сверху размером алфавита.Даже если размер алфавита больше размера строки, он все равно считается постоянным пробелом.

Существует много вариантов этой проблемы, многие из которых забавны.Чтобы сделать это действительно на месте, вы можете отсортировать в первую очередь;это дает O (n log n).Существуют варианты сортировки слиянием, когда вы игнорируете ошибки во время слияния.На самом деле, это ограничение «нет внешней хеш-таблицы» появляется в Алгоритм: эффективный способ удаления дублирующихся целых чисел из массива (также помеченный как вопрос интервью).

Другой распространенный вопрос интервью начинается с простогострока, потом говорят, ладно, теперь строка из миллиона символов, ладно, теперь строка из 100 миллиардов символов и так далее.Все становится очень интересным, когда вы начинаете рассматривать большие данные.

В любом случае, ваша идея довольно хороша.Как правило, его можно настроить следующим образом: используйте набор, а не словарь.Пройдите через строку.Для каждого символа, если его нет в наборе, добавьте его.Если это так, удалите это.Наборы занимают меньше места, не нуждаются в счетчиках и могут быть реализованы в виде наборов битов, если алфавит мал, и этот алгоритм не требует двух проходов.

Реализация Python: http://code.activestate.com/recipes/52560-remove-duplicates-from-a-sequence/

Answer 2

Вы также можете использовать битовый набор вместо дополнительного массива для отслеживания найденных символов.В зависимости от того, какие символы (az или более) разрешены, вы соответственно изменяете размер набора битов.Это требует меньше места, чем целочисленный массив.