avatar

Задача

Спросил ,
Итак, по просьбе Fortunato выкладываю задачку.
Задача: Доказать, что массив N является перестановкой массива M. Выбрать наиболее быстрый алгоритм (большим плюсом будет ещё показать его эффективность).
Первый решивший — молодец и няша ^_^

9 ответов

avatar
Что такое массив?
avatar
Набор однотипных элементов, расположенных в памяти друг за другом :)
avatar
Не, я так не играю. Могу осилить задачи вроде: А и Б сидели на трубе…
avatar
Я вообще крайне сомневаюсь, что хоть кто-то из здешних «программистов» сможет решить её :) Время покажет. Через пару дней напишу ответ.
avatar
Можно решить так: из массива M находить-и-удалять элементы массива N по одному. Если какой-либо элемент N не найден в M ИЛИ дойдя до последнего элемента массива N в массиве M останется хотя бы один элемент — значит они не являются перестановкой.
На простом неотсортированном массиве M сложность поиска элемента O(M) а удаления O(1) + мы проходим по массиву N, тогда сложность алгоритма будет O(N*M).
Однако, при смене контейнера, к примеру, на хешированный словарь, можно сократить сложность поиска до O(logM), тогда и общая сложность алгоритма упадет.
Что скажете? Комментарии? Замечания? Предложения?
avatar
А если не менять массив на хешированный?:) Составление хешированного массива тоже имеет сложность.
avatar
А переставлен он случайно? Какой тип данных? Любой?
avatar
Да, просто два разных случайных массива. Тип данных любой, который можно сравнить :)
avatar
Пора закрывать задачку.
Если отсортировать оба массива, после чего просто сравнить их, можно получить O(nlogn) (n==m, иначе вообще проверять перестановки нет смысла), что является оптимальным.
Только зарегистрированные и авторизованные пользователи могут отвечать на вопросы.