Определение, является ли последовательность T сортировкой последовательности S за O (n) времени

Question

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

То есть кто-то может иметь алгоритм, который выводит некоторую последовательность T, которая действительно находится в отсортированномпорядок, но не может содержать какие-либо элементы из последовательности S, так как мы можем проверить, что T действительно является отсортированной последовательностью S за O (n) времени?

Answer 1

1. Получите длину L из S.
2. Также проверьте длину T.Если они различаются, все готово!
3. Пусть Hs будет хеш-картой с чем-то вроде 2L блоков всех элементов в S.
4. Пусть Ht будет хешКарта (опять же, с 2L сегментами) всех элементов в T.
5. Для каждого элемента в T, проверьте, что он существует в Hs.
6. Для каждого элементав S проверьте, что он существует в Ht.

Это будет работать, если элементы уникальны в каждой последовательности.См. Ответ wcdolphin о небольших изменениях, необходимых для его работы с неуникальными последовательностями.

Я НЕ учел потребление памяти.Создание двух хэш-карт двойного размера каждой последовательности может быть дорогостоящим.Это обычный компромисс между скоростью и памятью.

Answer 2

Хотя ответ Эмиля очень хороший, вы можете сделать немного лучше.

По сути, для того, чтобы T был переупорядочением S, он должен содержать все одинаковые элементы. То есть для каждого элемента в T или S они должны встречаться одинаковое количество раз. Таким образом, мы будем:

Создать хэш-таблицу всех элементов в S, сопоставляя «Элемент» с числом вхождений.

Итерация по каждому элементу в T, уменьшение числа повторений текущего элемента.

Если число вхождений равно нулю, удалите его из хэша.

Если текущий элемент не находится в хэше, T не является переупорядочением S.

Answer 3

Я считаю, что это проблема O (n ^ 2), потому что:

1. Предполагая, что структура данных, которую вы используете для хранения элементов, представляет собой связанный список для минимальных операций по удалению элемента
2. Вы будете делать S.contains (элемент T) для каждого элемента T, и один будет проверять, имеют ли они одинаковый размер.
3. Вы не можете предполагать, что s упорядочен и, следовательно, нужно сделатьпоэлементное сравнение для каждого элемента.
4. наихудший случай будет, если S обратен к T
5. Это будет означать, что для элемента (0 + x) из T вы будете выполнять (nx) сравненияесли вы удаляете каждый успешный элемент.
6. это приводит к (n * (n + 1)) / 2 операциям, что составляет O (n ^ 2)

Может быть, какой-то другой умнееалгоритм там, хотя

Answer 4

Создание хэш-карты обеих последовательностей. Используйте символ в качестве ключа, а количество символов в качестве значения. Если персонаж еще не добавлен, добавьте его со счетом 1. Если персонаж уже добавлен, увеличьте его количество на 1.

Убедитесь, что для каждого символа во входной последовательности хэш-карта отсортированной последовательности содержит символ в качестве ключа и имеет то же значение, что и значение.