Как освоить оперативные алгоритмы модификации массива?

Примерно время O (n), алгоритм пространства O (1) для перетасовки

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

В следующей статье есть решение для времени O (n) и пространства O (1) (хотя оно предназначено для перетасовки, но выполнение перетасовки делает перетасовку тривиальной):

http://arxiv.org/PS_cache/arxiv/ pdf / 0805 / 0805.1598v1.pdf

О методе решения алгоритмов изменения массива на месте

Алгоритмы изменения на месте могут стать очень сложными для обработки.

Рассмотрим пару:

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

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

Тем не менее, для модификаций массива, которые приводят к перестановке исходного массива, вы можете попробовать метод после циклов перестановки . В принципе, любую перестановку можно записать как непересекающийся набор циклов (см. Также ответ Джона).Например, перестановка:

1 4 2 5 3 6

из 1 2 3 4 5 6 может быть записана как

1 -> 1
2 -> 3 -> 5 -> 4 -> 2
6 -> 6.

, стрелку можно прочитать как «идет к».

Итак, чтобы переставить массив 1 2 3 4 5 6 , вы следуете трем циклам:

1 переходит к 1.

6 переходит к 6.

2 переходит к 3, 3 переходит к 5, 5 переходит к 4 и 4 переходит к 2.

Чтобы следовать этому длинному циклу, вы можете использовать только одну временную переменную. Храните в нем 3 штуки. Поместите 2, где было 3. Теперь поместите 3 в 5 и сохраните 5 для температуры и так далее. Поскольку вы используете только постоянное дополнительное временное пространство для выполнения определенного цикла, вы выполняете модификацию массива на месте для этого цикла.

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

Разумный выбор начальных точек циклов может упростить алгоритм. Если вы придумали начальные точки в пространстве O (1), теперь у вас есть полный алгоритм на месте. Здесь вам, возможно, придется познакомиться с проблемой и использовать ее свойства.

Даже если вы не знали, как вычислять начальные точки циклов, но у вас была формула для вычисления следующего элемента, вы могли бы использовать этот метод, чтобы получить алгоритм времени на месте O (n) в некотором специальном случаи.

Например: если вы знали, что массив целых чисел со знаком содержит только положительные целые числа.

Теперь вы можете следить за циклами, но отрицать числа в них как индикатор «посещенных» элементов.Теперь вы можете пройтись по массиву и выбрать первое попавшееся положительное число и проследить для этого циклы, делая элементы цикла отрицательными и продолжая находить нетронутые элементы. В конце вы просто снова делаете все элементы положительными, чтобы получить результирующую перестановку.

Вы получаете алгоритм O (n) времени и O (1) пространства! Конечно,мы как бы «обманули», используя знаковые биты целых чисел массива в качестве нашего личного «посещенного» растрового изображения.

Даже если массив не обязательно был целыми числами, этот метод (следование циклам, а не взлом знаковых битов :-)) на самом деле можно использовать для решения двух указанных вами проблем:

• Перемешивание (или отключение -shuffle) проблема : Когда 2n + 1 является степенью 3, можно показать (используя теорию чисел), что 1,3,3 ^ 2 и т. д. находятся в разных циклах, и все циклы покрываются с их помощью. Объедините это с тем фактом, что перетасовка восприимчива к разделению и победе, вы получите алгоритм времени O (n) и пространства O (1) (формула i -> 2 * i по модулю 2n + 1). Обратитесь к вышеупомянутой статье для получения более подробной информации.

• Циклический сдвиг в задаче массива : Циклический сдвиг массива размера n на k также дает перестановку результирующего массива (задаваемый формулой i переходит в i + k по модулю n), и также может быть решен в линейное время и на месте, используя следующий метод цикла. Фактически, с точки зрения количества замен элементов этот метод следующего цикла лучше , чем алгоритм 3 реверса. Конечно, следование циклическому методу может убить кеш из-за шаблонов доступа, и на практике алгоритм 3 реверса может оказаться лучше.

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

Основная стратегия с алгоритмами in place состоит в том, чтобы выяснить правило перемещения записи из слота N в слот M.

Итак, например, ваша тасовка. если A и B - карты, а N - число карт. Правила для первой половины колоды отличаются от правил для второй половины колоды

 // A is the current location, B is the new location.
 // this math assumes that the first card is card 0
 if (A < N/2)
    B = A * 2;
 else
    B = (A - N/2) * 2 + 1;

Теперь мы знаем правило, нам просто нужно переместить каждую карту, каждый раз, когда мы перемещаем карту, мы вычисляем новое местоположение, затем удаляем карту, которая в настоящее время находится в B. Поместите A в слот B, затем пусть B будет A, и зацикливаемся на вершине алгоритма. Каждая перемещенная карта вытесняет новую карту, которая становится следующей картой для перемещения.

Я думаю, что анализ будет проще, если мы будем основываться на 0, а не на 1, так что

 0 1 2 3 4 5 6 7  // before
 0 4 1 5 2 6 3 7  // after

Итак, мы хотим переместить 1->2 2->4 4->1 и этим завершить цикл затем переместить 3->6 6->5 5->3 и это завершит цикл и мы закончили.

Теперь мы знаем, что карта 0 и карта N-1 не двигаются, поэтому мы можем их игнорировать, и мы знаем, что нам нужно поменять только N-2 карты. Единственный сложный момент заключается в том, что есть 2 цикла, 1,2,4,1 и 3,6,5,3. Когда мы доберемся до карты 1 во второй раз, нам нужно перейти к карте 1. во второй раз, нам нужно перейти к карточке 3.

 int A = 1;
 int N = 8;
 card ary[N]; // Our array of cards
 card a = ary[A];

 for (int i = 0; i < N/2; ++i)
 {
     if (A < N/2)
        B = A * 2;
     else
        B = (A - N/2) * 2 + 1;

     card b = ary[B];
     ary[B] = a;
     a = b;
     A = B;

     if (A == 1)
     {
        A = 3;
        a = ary[A];
     }
 }   

Теперь этот код работает только для примера с 8 картами из-за теста if, который переводит нас с 1 на 3, когда мы завершаем первый цикл. На самом деле нам нужно общее правило, чтобы распознать конец цикла и определить, где начать следующий.

Это правило может быть математическим, если вы можете придумать способ, или вы можете отслеживать, какие места вы посетили в отдельном массиве, и когда A возвращается к посещенному месту, вы можете сканировать вперед в вашем массиве в поисках первого непосещенного места.

Чтобы ваш алгоритм in-place был равен 0(n), решение должно быть математическим.

Я надеюсь, что это описание процесса мышления будет полезным для вас. Если бы я брал у вас интервью, я бы ожидал увидеть на доске нечто подобное.

Примечание: Как отмечает Moron, это не работает для всех значений N, это просто пример анализа, который ищет интервьюер.

Для первого предположим, что n четное. У вас есть:

первая половина: 1 2 3 4
вторая: 5 6 7 8

Пусть x1 = первая [1], x2 = вторая [1].

Теперь вам нужно напечатать один из первой половины, один из второй, один из первой, один из второй ...

Значение first [1], second [1], first [2], second [2] ], ...
Очевидно, вы не храните две половины в памяти, так как это будет O (n) памяти. Вы держите указатели на две половинки. Вы понимаете, как бы вы это сделали?

Второй вариант немного сложнее. Рассмотрим:
12345
abcde
.. cde
..... ab
.. cdeab
cdeab

Вы что-нибудь замечаете? Вы должны заметить, что вопрос в основном просит вас переместить первые символы i в конец вашей строки, не позволяя роскоши скопировать последние n - i в буфер, затем добавить первый i и затем вернуть буфер. Вам нужно делать с памятью O (1).

Чтобы понять, как это сделать, вам потребуется много практики с подобными проблемами, как и с любыми другими. Практика в основном приводит к совершенству. Если вы никогда раньше не сталкивались с подобными проблемами, вряд ли вы в этом разберетесь. Если да, то вы должны подумать о том, как вы можете манипулировать подстроками и / или индексами, чтобы решить вашу проблему при заданных ограничениях. Общее правило - работать как можно больше и узнавать как можно больше, чтобы вы очень быстро находили решения этих проблем, когда их видите, но решение довольно сильно отличается от проблемы к проблеме. Боюсь, что нет четкого рецепта успеха.Просто много читайте и поймите материал, который вы читаете, прежде чем двигаться дальше.

Логика второй проблемы такова: что произойдет, если мы перевернем подстроку [1, 2], подстроку [3, 5], а затем объединим их и перевернем? В общем, мы имеем:

1, 2, 3, 4, ..., i, i + 1, i + 2, ..., N
reverse [1, i] =>
i, i - 1, ..., 4, 3, 2, 1, i + 1, i + 2, ..., N
обратный [i + 1, N] =>
i, i - 1, ..., 4, 3, 2, 1, N, ..., i + 1
обратный [1, N] =>
i + 1, ..., N, 1, 2, 3, 4, ..., i - 1, i
, что вы и хотели. Запись обратной функции с использованием памяти O (1) должна быть тривиальной.

Франк,

Что касается программирования с использованием циклов и массивов, ничто не сравнится с учебником Дэвида Грайса The Science of Programming . Я изучал его более 20 лет назад, и есть идеи, которые до сих пор использую каждый день. Это очень математично и потребует реальных усилий для овладения, но эти усилия многократно окупятся за всю вашу карьеру.

В общем, идея состоит в том, чтобы перебрать массив один раз, при этом

• сохраняя значение в той позиции, в которой вы находитесь, во временной переменной
• , находя правильное значение для этой позиции и записывая его
• , либо переходите к следующему значению, либо выясняете, что нужно сделайте со своим временным значением, прежде чем продолжить.