Переупорядочение элементов массива

Учитывая массив

[a1 a2 a3 ... an b1 b2 b3 ... bn c1 c2 c3 ...cn] 

без использования дополнительной памяти, как вы переупорядочиваете в массив

 [a1 b1 c1 a2 b2 c2 a3 b3 c3 ... an bn cn] 

Ваш вопрос также можно перефразировать как «Как сделать перенос матрицы на месте?». Чтобы понять, почему, представьте себе добавление новой строки после каждой подпоследовательности в обоих ваших массивах. Это превратит первый массив в матрицу NxM, а второй – в матрицу MxN.

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

Предполагая, что вы имеете в виду память O (1) (или в зависимости от модели O (log n)), а не дополнительную память , существует линейный алгоритм локального времени.

Этот документ: http://arxiv.org/abs/0805.1598 имеет алгоритм для случая, когда у вас есть

a1 ... an b1 ... bn и хотите преобразовать в

b1 a1 b2 a2 ... bn an .

В документе также упоминается, что вы можете обобщить это на другие k-way shuffles. В вашем случае k = 3.

Алгоритм в статье даст следующее:

Начните с a1 a2 ... an b1 b2 ... bn c1 c2 ... cn и преобразуйте в

c1 b1 a1 c2 b2 a2 ... cn bn an

Другой проходит через это, и вы можете легко получить a1 b1 c2 a2 b2 c2 ... an bn cn .

Теперь, чтобы обобщить алгоритм в работе, нам нужно выбрать простое число p, такое, что k является примитивным корнем из p ^ 2.

При k = 3 будет выполняться p = 5.

Теперь, чтобы применить алгоритм, сначала вам нужно найти наибольшее m

Примечание: это произойдет только тогда, когда 3m + 1 – четная мощность 5. Таким образом, вы можете работать с полномочиями 25 при попытке найти m. (5 ^ нечетное – 1 не делится на 3).

Когда вы найдете m,

Вы перетасовываете массив, чтобы

[a1 a2 ... am b1 b2 ... bm c1 c2 ... cm] [a(m+1) ... an b(m+1) ... bn c(m+1) ... cn]

а затем использовать следующий метод цикла (см. статью) для первых 3m элементов, используя полномочия 5 (включая 1 = 5 ^ 0) в качестве отправных точек для разных циклов) и выполнить хвостовую рекурсию для остальных.

Теперь для преобразования a1 a2 ... an b1 b2 ... bn c1 c2 ... cn

в

[a1 a2 ... am b1 b2 ... bm c1 c2 ... cm] [a(m+1) ... an b(m+1) ... bn c(m+1) ... cn]

вы сначала делаете циклический переход, чтобы получить

a1 a2 ... am [b1 b2 bm a(m+1) .. an] b(m+1) .. bn c1 c2 ... cn

(элементы в квадратных скобках – это те, которые были сдвинуты)

Затем сделайте циклический сдвиг, чтобы получить

a1 a2 ... am b1 b2 bm a(m+1) .. an [c1 c2 ..cm b(m+1) .. bn ] c(m+1) ... cn

И затем окончательный переход на

a1 a2 ... am b1 b2 bm [c1 c2 ..cm a(m+1) .. an ] b(m+1) .. bn c(m+1) ... cn

Обратите внимание, что циклический сдвиг может выполняться в O (n) времени и O (1) пространстве.

Таким образом, весь алгоритм – это O (n) время и O (1) пространство.

Вы можете вычислить целевую позицию каждого элемента на основе его индекса.

 groupSize = N/3 group = i/groupSize rank = i - group * groupSize dest = rank * 3 + group 

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


В качестве альтернативы вы можете сделать это без каких-либо дополнительных бит за счет перехода на полиномиальное время. Переверните вычисление, чтобы вы могли найти исходный индекс источника для каждого элемента в конечном массиве.

 source = i % groupSize + groupSize * (i/groupSize) ; //integer division 

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

 getSource(i): s = i % groupSize + groupSize * (i/groupSize) while (s 

Вы можете сделать это наверняка – просто возьмите карты туза, 2, … 5 в 3 костюмах и приведите их в порядок.

Сначала вы вынимаете карту a2 и откладываете ее. Затем вы перемещаете b1 в позицию a2 и сдвигаете все карты вверх

Затем вы положили карту a2 и вставили в сдвинутое положение.

Затем вы берете карту a3 и puti taside. Переместите c1 в позицию a3 и сдвиньте все карты вверх.

Затем верните карту a3 в опустошенное положение.

повторить до конца.

Фактический расчет индексов сложный, но я считаю, что предыдущий плакат сделал это.

  • Как добавить рабочие дни в текущую дату на Java?
  • Двоичный поиск в массиве
  • Побитовое и вместо оператора модуля
  • Как ускорить алгоритм A * при больших пространственных масштабах?
  • Алгоритмы заполнения паводков
  • Почему мы используем Base64?
  • максимальный подмассив массива с целыми числами
  • Поиск отверстий в 2d точечных множествах?
  • Алгоритм поиска наименьших прямоугольников для покрытия набора прямоугольников без перекрытия
  • Временная сложность алгоритма Евклида
  • TMP: как обобщить декартово произведение векторов?
  • Давайте будем гением компьютера.