Две красивые задачи по алгоритмам

На этой неделе я начал читать бакалаврам Академического университета базовый курс по алгоритмам. Начинал я совсем с основ, и чтобы тем, кто с базовыми алгоритмами уже знаком, было чем заняться, я в начале пары сформулировал две, наверное, самые свои любимые задачки по алгоритмам. Давайте и с вами ими поделюсь. Решение одной из них даже под катом подробно расскажу. Но не отказывайте себе в удовольствии и не заглядывайте сразу под кат, а попытайтесь решить задачи самостоятельно. Обещаю, что у обеих задач есть достаточно простые решения, не подразумевающие никаких специальных знаний по алгоритмам. Это, конечно, не означает, что эти решения просто найти, но после пары один из студентов подошёл и рассказал правильное решение первой задачи. =) Если же вам интересно посмотреть на начало курса или порешать больше разных задач — приходите к нам на (бесплатный) онлайн-курс, который начнётся 15 сентября.

Задача 1. Дан массив A длины (n+1), содержащий натуральные числа от 1 до n. Найти любой повторяющийся элемент за время O(n), не изменяя массив и не используя дополнительной памяти.

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

Задача 2. Дана матрица nxn, содержащая попарно различные натуральные числа. Требуется найти в ней локальный минимум за время O(n).

Локальным минимумом матрицы называется элемент, который меньше всех своих четырёх соседей (или трёх, если этот элемент лежит на границе; или двух, если это угловой элемент). Обратите внимание, что от нас требуется линейное по n время, хотя в матрице квадратичное по n число элементов. Поэтому мы предполагаем, что матрица уже считана в память. И нам нужно найти в ней локальный минимум, обратившись лишь к линейному количеству её ячеек.

Под катом — решение первой задачи. Ещё раз призываю вас заглядывать под кат только после того, как порешаете задачу. По второй задаче могу какую-нибудь подсказку сказать.

Попытаюсь рассказать не только решение, но и то, как до него можно было бы догадаться. Пояснять буду сразу на примере. Из него, надеюсь, будет понятно, как алгоритм работает в общем случае. Рабочий пример:

То есть нам дан массив длины 9, содержащий числа от 1 до 8, и наша цель — найти двойку или пятёрку.

Как мы помним, использовать дополнительную память в условии задачи запрещено. Давайте, однако, поймем, чем она могла бы нам помочь. Мы бы тогда завели новый массив размера n и одним проходом по исходному массиву A посчитали бы, сколько раз каждое из чисел от 1 до n входит в A. По этому массиву было бы сразу видно, кто в A повторяется.

Это в дальнейшем не особо нам поможет, но всё же.

Ограничение на дополнительную память не даёт нам собрать и записать вспомогательную информацию о массиве. Значит, повторяющийся элемент нам нужно найти, как-то «гуляя» по массиву. Гулять по массиву можно слева направо, например, но непонятно, какую информацию можно при этом извлечь. Поэтому попробуем гулять по-другому. Встанем в первый элемент нашего массива и посмотрим, что там написано. Написано там число 7, поэтому давайте посмотрим на седьмой элемент массива. Там записано число 1. Прогулка получилась недолгой, мы зациклились. То, что в массиве есть какие-то циклы, очень нам поможет в дальнейшем. Для примера давайте ещё попробуем прогуляться из второго элемента: оттуда мы пойдём в элемент номер 5, из него — в элемент номер 3, а из элемента номер 3 опять вернёмся обратно в элемент номер 2. То есть нашли ещё один цикл. Давайте изобразим найденные нами два цикла:

И раз уж мы осознали, что наш массив неявно задаёт некоторый граф, то давайте явно этот граф нарисуем. Формально, вершины графа — это числа от 1 до n+1; мы проводим ориентированное ребро из i в j, если A[i]=j.

Интересуют нас в этом графе вершины, в которые входят хотя бы два ребра (если в вершину j входят рёбра из вершин i и k, то A[i]=A[k]=j, то есть j повторяется в массиве A). Нам и так ясно, что такая вершина в графе есть, но давайте это осознаем ещё раз, в терминах графов. В нашем графе из каждой вершины выходит ровно одно ребро (и значит, в графе (n+1) ребро), но есть одна вершина, в которую ничего не входит: это вершина (n+1). Значит, найдётся вершина, в которую входит хотя бы два ребра. В общем-то, это и так было ясно, но вот замечание про вершину (n+1) нам в дальнейшем поможет.

Давайте встанем в вершину (n+1) и будем переходить в нашем графе по исходящим рёбрам. Когда-нибудь мы зациклимся, конечно, но важно то, что мы не вернёмся в вершину (n+1). В нашем рабочем примере мы выйдем из вершины 9 и дойдём до цикла (5,2,3). Видно, что точка входа в этот цикл — это и есть повторяющийся элемент: ведь в эту точку и по ребру цикла можно войти, и по ребру на пути из вершины (n+1) в цикл. В нашем примере такая точка входа — это вершина 5.

Нахождение этой точки — отдельная не слишком простая задача, но её решение очень похоже на решение стандартной задачи о зацикленности списка. Длину цикла найти несложно. Например, сделаем n+1 шаг из вершины n+1. После этого мы обязательно окажемся в вершине на цикле. Запомним эту вершину и будем продолжать шагать, пока не вернёмся в неё. Тем самым узнаем длину цикла k. Теперь сделаем следующее. Поставим два указателя в вершину n+1. Первым указателем сделаем k шагов. После этого будем двигать каждый из указателей на один шаг вперёд, пока они не встретятся (таким образом, первый указатель всегда будет обгонять второй на k шагов). Ясно, что встретятся эти ребята как раз в нужной нам точке входе. В нашем примере длина цикла равна трём. После трёх шагов первый указатель окажется в вершине 2. В этот момент мы начнём двигать и второй указатель. Через два шага указатели встретятся в вершине 5.

На закуску. Мы не обсудили, почему же было запрещено модифицировать массив (и наш алгоритм массив, действительно, не трогал). Придумайте более простое решение, если разрешается портить массив.

Автор: alexanderskulikov

Источник