Никто не пробовал писать алгоритм циклического сдвига массива?
Я опробовал несколько примеров, придумал алгоритм и реализовал его:
public static void shiftRight(int[] array, int step) {
final int length = array.length / step;
for (int i = 0; i < step; i++) {
for (int j = 0, k = i; j < length; j++) {
k += step;
if(k >= array.length) {
k -= array.length;
}
swap(array, i, k);
}
}
}
Получилось что-то такое... Работает. Но иногда даёт сбой. Например:
Входной массив: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Выходной массив: [4, 5, 8, 9, 6, 7, 0, 1, 2, 3]
Принцип алгоритма таков:
Мы меняем местами нужные ячейки массива. Начинаем с нулевой ячейки до ячейки step.
1. Выбираем ячейку i и будем её менять со всеми другими ячейками j (так как нам задан шаг step - очевидно, что следующей ячейкой j будет j = i + step, и далее будет возрастать с таким же шагом j += step. Так как сдвиг у нас циклический, то j >= length -> j -= length)
2. Количество таких изменений определяется по формуле: l = length / step с округлением вниз (взял с примеров, всегда работает)
После замены всех ячеек массив сдвигается на step вправо с цикличностью. Пример:
[0, 1, 2, 3, 4] >> 2 = ?
step = 2
l = length / step = 5 / 2 = 2
1. i = 0, j = i + step = 2 | => [0, 1, 2, 3, 4] -> [2, 1, 0, 3, 4]
2. i = 0, j += step = 4 | => [2, 1, 0,3, 4] -> [4, 1, 0, 3, 2]
3. i = 1, j = i + step = 3 | => [4, 1, 0, 3, 2] -> [4, 3, 0, 1, 2]
4. i = 1, j += step = 5, j >= length -> j -= length = 0 | => [4, 3, 0, 1, 2] -> [3, 4, 0, 1, 2]
Получилось... И с другими примерами получалось. И решение выглядит,
вроде, логичным. Может кто-то заметил какой-то недочёт или ошибку?
Скопировать ссылку
Перейти к посту
Фильтровать сообщения
Файлы топика (2)
let live
Пользователь
