Скольжение массива в Java - алгоритм основан

Question

Я пишу программу на Java, в которой мне нужно сдвинуть элементы массива, и она должна выполнять как можно меньше операций, так как она находится внутри двойного цикла, и я работаю с длиной массива, начиная отдо 10 ^ 8.

Пример: A = {1,2,3,4,5,6} Результат: A = {2,3,4,5,6,1} в первый раз A ={3,4,5,6,1,2} во второй раз и так далее.

Пожалуйста, не стесняйтесь предлагать любую другую структуру данных или любые модификации массива !!Спасибо вам, ребята!!: D

Answer 1

Самый простой способ добиться этого эффекта - создать «круговой массив»; то есть вместо перемещения содержимого массива вы можете просто сохранить индекс, который отмечает начало массива.

Чтобы получить элемент по индексу i, вам нужно:

Type item = arr[(offset + i) % arr.length];

Таким образом, вы получаете те же свойства, что и в массиве, и можете выполнять любое вращение в O (1).

Чтобы сделать это менее сложным в использовании, вы можете создать простой класс-обертку, который просто оборачивает массив, позволяя легко вращаться через этот метод. Таким образом, код может выглядеть чистым, а вы получите эффективный поворот.

Answer 2

Чтобы достичь сложности O (1), вы могли бы ...

1. использовать связанный список
2. Оберните ваш массив классом, который хранит начальную позицию и позволяет вам получить доступ к массиву через «виртуальные» индексы (wrapped.acces (i) => array [(start + i)% array.length]
3. «удвоить» массив и нарезать его соответствующим образом (чтобы вам не приходилось изменять окружающий код)

В противном случае, если вы хотите придерживаться своей структуры данных, вам нужно заплатить O (n), несмотря ни на что.

Я бы пошел с (2), потому что это быстрее и для произвольного доступа, и для шаблонов линейного доступа (массивы имеют лучшую локальность данных + O (1) сложность произвольного доступа без O (n) связанных списков).

Answer 3

Использование Collections.rotate(Arrays.asList(myArray), myDistance).

Answer 4

Если вы не женаты на идее использования массивов, то вы можете использовать метод Collections.rotate ().

List<Integer> list = new ArrayList<Integer>();

for (int i = 1; i <= 6; i++) {
    list.add(i-1, new Integer(i));
}

int j = 0;
while (j < 100) {
    Collections.rotate(list, -1);
    System.out.print("{");
    for (Integer integer : list) {
        System.out.print(integer + ", ");
    }
    System.out.println("}");
}

Answer 5

Почему вы должны вращать стол?

Представьте, что стол - это круг, и после этого вы можете ходить так:

Object object = array[(offset + i) % array.length];

Это дает вам O (1) на любом шаге доступа или поворота;

Answer 6

Вы можете использовать простой список для этого.Если вы делаете это скольжение часто, лучшим выбором будет очередь.Дело в том, что массив на самом деле не меняется, вы просто начинаете читать в позиции x, а затем продолжаете читать в начале элементов длины (array) -x массива.Это самый быстрый вариант.