Как вы можете эффективно удалить повторяющиеся символы из строки?

Question

Можно ли удалить повторяющиеся символы из строки, не сохраняя каждый символ, который вы видели в массиве, и не проверяя, есть ли новые символы в этом массиве? Это кажется крайне неэффективным. Наверняка должен быть более быстрый метод?

Answer 1

Вы можете использовать логический массив , проиндексированный символом :

bool seen[256];

Для байтовых ASCII-подобных символов было бы целесообразно вышеуказанное. Для 16-битного Unicode:

bool seen[65536];

и так далее. Затем для каждого символа в строке это простой поиск, чтобы увидеть, был ли этот логический тип уже установлен.

Answer 2

Я не знаю, есть ли более простой алгоритм. Альтернативный способ - изучить первый символ, затем пройти остаток строки и удалить все одинаковые символы. Затем сделайте это для 2-го символа, 3-го символа и так далее. Это может сэкономить память, но будет O (n ^ 2).

Алгоритм, который вы предложили, будет O (n * m), m

Однако в большинстве реальных приложений я сомневаюсь, что эффективность предложенного вами метода окажет какое-либо заметное влияние на производительность. Вероятно, существуют другие методы (такие как регулярные выражения или различия LINQ), которые могут иметь еще большие накладные расходы, но, вероятно, стоили бы этого из-за упрощения кода.

Answer 3

Вы можете использовать регулярное выражение для совпадения с этими дублирующимися символами одновременно.

Answer 4

Использование linq

string someString = "Something I wrote quickly";
char[] distinctChars = someString.ToCharArray().Distinct();
string newString = new string(distinctChars);

Answer 5

Python:

>>> ''.join(set("Something I wrote quickly"))
' cegihkmlonqISrutwy'

Очевидно, это не сохраняет порядок.

Answer 6

Это будет зависеть от характеристик ваших данных. Строка очень длинная? Ожидается ли много дубликатов? Каков диапазон возможных символов в строке (это английский? Китайский?) Сколько памяти у вас есть? Нужно ли упорядочивать полученную строку?

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

Если строка действительно длинная, вы хотите, чтобы время выполнения было близко к O (n), что означает сохранение установленного бита (как правило) или, в более редких случаях, хеш (если список возможных символов большой: Китайский?) Или тому подобное и отслеживание символов, которые вы видели, чтобы вы могли выселить их, когда вы ходите по струне. Здесь также есть много деталей реализации, связанных с тем, нужно ли вам сдвигать назад всю оставшуюся строку в памяти каждый раз, когда вы удаляете символ, или вы можете заменить его пустым или чем-то еще на месте.

Итак, опять же, зависит от того, чего вы пытаетесь достичь, и в какой среде вы находитесь.