Java

Как сместить массив вправо java

Нужно циклически сдвинуть массив на К элементов в право

мой код:

import java.util.Scanner;

class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner( System.in );

int a = scanner.nextInt();
int b = scanner.nextInt();
int[] x = new int[a];
for (int i = 0; i < a; i++) {
x[i] = scanner.nextInt();
}

for (int i = 0; i < b; i++) {
int temp = x[x.length - 1];

for (int j = x.length - 1; j > 0; j--)
x[j] = x[j - 1];

x[0] = temp;
}
for (int i = 0; i < a; i++){
System.out.print(x[i] + " ");
}

}
}


Сдвиг нужно кратно обрезать числами, долгое время выполнения
КТ
Канторо Токтосунов
241
Алгоритм ужасен. Каждый элемент списка пропутешествует все позиции на пути своего сдвига. Сложность: O(a * b).
Есть намного более эффективные способы это сделать:
1) Завести временный массив длины b, сложить туда элементы из хвоста списка (от индекса a - b и далее до конца). Потом сдвинуть a - b элементов вправо за один проход (заметим, тут нужна итерация от больших индексов к меньшим). Потом переложить элементы из временного массива в первые b элементов основного массива. Вычислительная сложность O(a + b), расход дополнительной памяти O(b).
2) Перевернуть массив в обратном порядке. Перевернуть первые b элементов. Перевернуть последние a - b элементов. Вычислительная сложность O(a), расход дополнительной памяти O(1).
Дмитрий Гусев
Дмитрий Гусев
54 053
Лучший ответ
сдвиг цикличный?
может пример ввода и вывода покажешь?
Алексей Зубарев
Алексей Зубарев
81 914
Канторо Токтосунов Прошу прощения за долгий ответ. Добавил в код изменения, выполняется быстро, но без двойного цикла надо обойтись. Надо для каждого элемента считать сразу конечные позиции. Вот мой код:

int a = scanner.nextInt();
int b = scanner.nextInt();
int[] x = new int[a];
for (int i = 0; i < a; i++) {
x[i] = scanner.nextInt();
}
int x1 = b%a;
for (int i = 0; i < x1; i++){
int temp = x[x.length - 1];
for (int j = x.length - 1; j > 0; j--)
x[j] = x[j - 1];
x[0] = temp;
}
for (int s: x){
System.out.print(s + " ");
}
}
}

Пример 1
Входные данные
5 1
1 2 3 4 5
Выходные данные
5 1 2 3 4
Пример 2
Входные данные
5 10
1 2 3 4 5
Выходные данные
1 2 3 4 5
Можете помочь?
Ваш код выглядит правильным и должен работать для сдвига массива вправо на К элементов. Однако, если вы хотите улучшить производительность, вы можете использовать другой подход. Вместо того, чтобы сдвигать массив на один элемент за раз, вы можете использовать алгоритм, который сдвигает массив на К элементов за один проход. Например, вы можете использовать алгоритм из трех reverse для циклического сдвига влево, который легко запомнить и в реализации которого практически невозможно ошибиться. Вот как он работает с 12345 (s[] = 12345, size = 5, dist = 2):
 reverse(s, dist); // 21|345 

reverse(s + dist, size - dist); // 21|543 

reverse(s, size); // 34512
Вы можете адаптировать этот алгоритм для сдвига вправо.
Илья Трескин
Илья Трескин
25 860

Похожие вопросы