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

Ответ 1

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

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

Следующая бумага имеет O (n) время и O (1) пространственное решение (хотя это для встряхивания, но выполнение встряхивания делает излишним тривиальным):

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

О методе решения встроенных алгоритмов модификации массива

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

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

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

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

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

1 4 2 5 3 6

of 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) пространственный алгоритм! Конечно, мы как бы "обманули", используя биты знака целых чисел массива в качестве нашего личного "посещенного" растрового изображения.

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

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

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

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

Ответ 2

Основная стратегия с использованием алгоритмов на месте - это выяснить правило перемещения записи из слота 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. place 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, во второй раз нам нужно перейти на карту 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 возвращается в посещенное место, вы можете затем пересканировать вперед в своем массиве в поисках первого не посещаемого места.

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

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

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

Ответ 3

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

первая половина: 1 2 3 4
секунда: 5 6 7 8

Пусть x1 = сначала [1], x2 = second [1].

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

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

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

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

Ответ 4

Франк,

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

Ответ 5

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

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

Ответ 6

Дополняя ответ Aryabhatta:

Существует общий метод "следовать циклам", даже не зная начальных позиций для каждого цикла или используя память, чтобы знать посещенные циклы. Это особенно полезно, если вам нужна память O (1).

Для каждой позиции я в массиве следуйте циклу, не перемещая никаких данных, пока вы не достигнете...

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

Конечно, у этого есть временные накладные расходы (O (n ^ 2), я полагаю) и имеет проблемы с кешем общего метода "следующих циклов".

Ответ 7

Общий подход может быть следующим:

• Построить массив позиций int [] pos, так что pos [i] ссылается на позицию (индекс) для [i] в ​​перетасованном массиве.

• Переупорядочить исходный массив int [] a, в соответствии с этим положением array pos.

  /** Shuffle the array a. */    
  void shuffle(int[] a) {
      // Step 1
      int [] pos = contructRearrangementArray(a)
      // Step 2
      rearrange(a, pos);
  }
  
  /**
   * Rearrange the given array a according to the positions array pos.
   */
  private static void rearrange(int[] a, int[] pos)
  {
      //  By definition 'pos' should not contain any duplicates, otherwise rearrange() can run forever.
     // Do the above sanity check.
      for (int i = 0; i < pos.length; i++) {
          while (i != pos[i]) {
              // This while loop completes one cycle in the array
              swap(a, i, pos[i]);
              swap(pos, i, pos[i]);
          }
      }
  }
  
  /** Swap ith element in a with jth element. */
  public static void swap(int[] a, int i, int j) 
  {
      int temp = a[i];
      a[i] = a[j];
      a[j] = temp;
  }
  

В качестве примера для случая outShuffle следующее будет представлять реализацию contructRearrangementArray().

/**
 * array     : 1 2 3 4 5 6 7 8
 * pos       : 0 2 4 6 1 3 5 7
 * outshuffle: 1 5 2 6 3 7 4 8 (outer boundaries remain same)
 */
public int[] contructRearrangementArray(int[] a)
{
    if (a.length % 2 != 0) {
        throw new IllegalArgumentException("Cannot outshuffle odd sized array");
    }
    int[] pos = new int[a.length];
    for (int i = 0; i < pos.length; i++) {
        pos[i] = i * 2 % (pos.length - 1);
    }
    pos[a.length - 1] = a.length - 1;
    return pos;
}