Сдвиг элементов массива java

Сдвиг элементов массива java

Сайт о том, как стать программистом и как с этим жить потом

Не так давно стартовал очередной курс Java на одном небезызвестном образовательном портале. И вот, моим студентам досталась задача по работе с массивами. Статья в первую очередь для них, но и для интересующихся, конечно же 🙂 Отдельное спасибо alexandr.baykov@gmail.com за комментарий по поводу массива с чётным количеством элементов и чётным размером сдвига. Я переписал алгоритм и обновил статью.

Итак, задача сформулирована следующим образом

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

Усложняющее условие было введено потому, что можно решить задачу при помощи разделения массивов. В таком случае решение состоит в том, чтобы «отрезать» от массива кусок длиной n справа или слева (в зависимости от того, как n сравнивается с 0) и «прикрепить» отрезанную часть обратно с другой стороны. Это довольно дешёвый алгоритм, который имеет сложность O(n), но он будет требовать дополнительной памяти для хранения временного массива размера n. Поскольку такое решение самое простое, да и не особенно подходит под условие задачи, то мы перейдём сразу к более сложной алгоритмизации.

Разумеется, после первых подходов многие студенты находят следующее довольно логичное и вполне корректное решение. Оно весьма популярно на различных сайтах, описывающих циклический сдвиг. Суть его в том, что любой сдвиг можно представить в качестве n сдвигов на 1 ячейку. Сдвиг на 1 ячейку довольно просто реализуется циклом. В итоге, если изобразить это Java-методом, получается примерно такой метод:

public static int [ ] shiftArray ( int [ ] incomingArray, int shift ) <
if ( shift != 0 ) <
// Любой сдвиг больше длины массива можно оптимизировать до меньшего сдвига
// через деление по модулю

int finalShift ;
if ( shift > incomingArray. length ) <
shift = Math . abs ( shift % incomingArray. length ) ;
>
else <
finalShift = shift ;
>

// в зависимости от знака сдвига движение будет происходить
// слева направо при положительном сдвиге
// справа налево при отрицательном
if ( shift > 0 ) <
for ( int n = 0 ; n shift ; n ++ ) <
// убираем первый элемент в буфер, а на его место ставим хвостовой элемент
int buffer = incomingArray [ 0 ] ;
myArray [ 0 ] = incomingArray [ incomingArray. length — 1 ] ;

Читайте также:  Термометр на кр572пв2 схема

// циклично сдвигаем весь массив
for ( int j = 1 ; j incomingArray. length — 1 ; j ++ ) <
incomingArray [ incomingArray. length — j ] = incomingArray [ incomingArray. length — j — 1 ] ;
>

// ставим буферный элемент в 1 ячейку
incomingArray [ 1 ] = buffer ;
>
>
else if ( shift 0 ) <
for ( int i = 0 ; i > shift ; n — ) <
int buffer = incomingArray [ incomingArray. length — 1 ] ;
incomingArray [ incomingArray. length — 1 ] = incomingArray [ 0 ] ;

for ( int j = 1 ; j incomingArray. length — 1 ; j ++ ) <
incomingArray [ j — 1 ] = incomingArray [ j ] ;
>

incomingArray [ incomingArray. length — 2 ] = buffer ;
>
>
>

Хочу отметить, что такое решение имеет место, и оно применимо. Но мы же решаем алгоритмическую задачу, поэтому неплохо бы поговорить о том, какую сложность будет иметь приведенный алгоритм. Если опустить процесс вычислений буферных элементов и обмена ими между ячейками, то сложность алгоритма сводится к O(N * M), где N — размер входного массива, а M — величина сдвига. Очевидно, что для |M| = 1 (т.е. M = -1 или M = 1) сложность снизится до O(N). Это частный случай.

Теперь давайте подумаем, что же тут не так. На самом деле, если мы знаем величину сдвига (а мы её знаем), то вполне можно вычислить, какой элемент будет следующим. Это говорит о том, что можно создать жонглирующий алгоритм следующего вида:

  1. Получаем нулевой элемент и кладем его в буфер
  2. Начинаем цикл от 0 до длины массива включительно (это обусловлено тем, что в момент, когда мы дойдём до последнего элемента, он будет помещен в буфер, из которого его надо восстановить на месте нулевого элемента, чем полностью закольцевать сдвиг)
  3. Дальше мы меняем местами элементы, исходя из размера шага. Например, для шага 3 и массива длиной 7 мы сначала поменяем элементы 0, 3, 6. Затем — 1, 4, 2. И так далее.

Если рассмотреть наборы изменяемых элементов, то мы увидим, что количество таких наборов, внутри которых мы будем итеративно менять местами элементы, будет равно наименьшему общему делителю для размера массива и размера сдвига. К примеру, для массива из 12 элементов при сдвиге 3 мы будем иметь три набора смещаемых элементов.

Читайте также:  Нарисовать машину в паскале abc

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12

— 1, 4, 7, 10
— 2, 5, 8, 11
— 3, 6, 9, 12

4 5 6 7 8 9 10 11 12 1 2 3

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

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

Теперь мы можем написать реализацию нашего алгоритма

public class moves <

public static void main ( String [ ] args ) <
int [ ] in1 = < 5 , 3 , 7 , 2 , 9 , 13 , 42 >;
int [ ] out1 = moves ( in1, — 2 ) ;
printOut ( out1 ) ;

int [ ] in2 = < 5 , 3 , 7 , 2 , 9 , 13 , 42 , 43 , 45 , 46 >;
int [ ] out2 = moves ( in2, 2 ) ;
printOut ( out2 ) ;

int [ ] in3 = < 5 , 3 , 7 , 2 , 9 , 13 , 42 , 143 >;
int [ ] out3 = moves ( in3, 5 ) ;
printOut ( out3 ) ;

int [ ] in4 = < 5 , 3 , 7 , 2 , 9 , 42 , 43 , 45 , 46 >;
int [ ] out4 = moves ( in4, 0 ) ;
printOut ( out4 ) ;
>

/**
* Main method, shifts array
* @param incoming — user array
* @param delta — shift value
* @return int[] result array
*/
static int [ ] moves ( int [ ] incoming, int delta ) <
int currentIndex, movedIndex, buffer ;
for ( int i = 0 ; i greatestCommonDivisor ( delta, incoming. length ) ; i ++ ) <
buffer = incoming [ i ] ;

if ( delta > 0 ) <
while ( true ) <
movedIndex = currentIndex + delta ;
if ( movedIndex >= incoming. length )
movedIndex = movedIndex — incoming. length ;
if ( movedIndex == i )
break ;
incoming [ currentIndex ] = incoming [ movedIndex ] ;
currentIndex = movedIndex ;
>
>
else if ( delta 0 ) <
while ( true ) <
movedIndex = currentIndex + delta ;
if ( movedIndex 0 )
movedIndex = incoming. length + movedIndex ;
if ( movedIndex == i )
break ;

incoming [ currentIndex ] = incoming [ movedIndex ] ;
currentIndex = movedIndex ;
>
>

incoming [ currentIndex ] = buffer ;
>

/**
* Simple printout
* @param incomingArray user array
*/
public static void printOut ( int [ ] incomingArray ) <
for ( int item : incomingArray ) <
System . out . print ( item + " " ) ;
>

/**
* Finding the GCD in recoursive function
* @param a — first element
* @param b — second element
* @return int GCD
*/
static int greatestCommonDivisor ( int a, int b )
<
if ( b == 0 )
return a ;
else
return greatestCommonDivisor ( b, a % b ) ;
>
>

Читайте также:  Windows 10 интересное не работает

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

Надеюсь, приведенные измышления будут для Вас полезны. Буду рад критике и комментариям!

Дочитавшим до конца, картинка де мотиватор &#128578;

Я пишу шифр SDES в Java, попасть на сцену, где я сдвиг два массива длиной 5 один пространство слева, это работает отлично для p10kleft стать shiftp10kleft, но когда я применяю тот же код для p10kright стать shiftp10kright его добавляет случайную 1 в конце вместо сдвига первых 0, чтобы стать последним битом.

Мне нужно сдвиг вправо, чтобы правильно выход [1, 0, 0, 1, 0]

Как и в комментариях, хранящих первое значение в примитив, прежде чем в цикле:

Что касается другого вопроса, повторяя эту операцию 3 раза, является очевидным (и не особенно умный, или эффективный способ), чтобы сделать это:

В любом случае , существует целый ряд более эффективных способов сделать это, как я уже предлагал. Если вы решительно настроены на массивы, однако, вы могли бы по крайней мере использовать System.arraycopy . Упрощенный пример будет выглядеть так :

И затем использовать его как это:

EDIT: закрепление порядка параметра в arraycopy .

У меня есть массив объектов Integer в Java, например, так:

Я бы хотел переместить все ненулевые позиции массива на одну позицию вправо и вставить "1" в позиции 0. Я не могу создать новый массив или использовать другие коллекции. Массив, который я получу в итоге, будет:

Как бы я мог это сделать без перезаписи элементов?

РЕДАКТИРОВАТЬ: Да, я дал идти на кодирование этого. Я здесь, потому что я застрял! Вот одна из попыток.

Ссылка на основную публикацию
Самая слабая видеокарта в мире
Источник: nvidia, amd, geforce gtx 280, geforce gtx 260, radeon hd 4850, radeon hd 4850 © 1997-2020 3DNews - Daily...
Ремонт аэрогриля хоттер своими руками видео
Когда вы обнаружите, что ваш аэрогриль не включается в работу, не спешите звонить в мастерскую. Есть много мелких неполадок, которые...
Решение уравнений третьей степени методом кардано
Схема метода Кардано Приведение кубических уравнений к трехчленному виду Сведение трёхчленных кубических уравнений к квадратным уравнениям при помощи метода Никколо...
Самсунг дуос как сбросить до заводских настроек
Пошаговая инструкция, как выполнить сброс настроек (hard reset) на мобильных телефонах и планшетах Samsung Galaxy: J3, J5, J6, J7, S8,...
Adblock detector