Тоже придумал сортировку.
Назвал ее LGBTranSort.
Итерируешь по элементам.
Если элемент is out of order, то он просто меняет гендерную идентичность
значение на подходящее (ну чтобы можно было нормально пристроиться к предыдущему
элементу).
Здравствуйте, Vi2, Вы писали:
C0s>>коллега предложил более экономный вариант — PolPotSort с мощностью O(1). На выходе — сразу пустой список.
Vi2>Более корректно, выдавать список, состоящий из первого(последнего) элемента: вот он уж точно отсортированный.
но тогда приходится проверять на непустоту — уже лишнее усложнение
Здравствуйте, bzig, Вы писали:
B>Задача на собеседовании: KgbSort — найти и удалить наименьший список "лишних" элементов, после которого список становится сортированным.
Ну и задачка...
O(2n) времени + O(n) памяти или можно быстрее?
Здравствуйте, B0FEE664, Вы писали:
BFE>O(2n) времени + O(n) памяти или можно быстрее?
Можно O(n2) времени + O(n) памяти. (Динамическое программирование.)
Здравствуйте, Chorkov, Вы писали:
BFE>>O(2n) времени + O(n) памяти или можно быстрее? C>Можно O(n2) времени + O(n) памяти. (Динамическое программирование.)
Алгоритм?
Здравствуйте, B0FEE664, Вы писали:
BFE>Здравствуйте, Chorkov, Вы писали:
BFE>>>O(2n) времени + O(n) памяти или можно быстрее? C>>Можно O(n2) времени + O(n) памяти. (Динамическое программирование.) BFE>Алгоритм?