Поворот массива на произвольный размер шага без создания второго массива

Question

Итак, для размера шага 1 я хочу массив:

{1, 2, 3, 4}

Стать:

{4, 1, 2, 3}

И для шага размера 2 результат будет:

{3, 4, 1, 2}

Это код, который я сейчас использую:

private static int[] shiftArray(int[] array, int stepSize) {
  if (stepSize == 0)
     return array;

  int shiftStep = (stepSize > array.length ? stepSize % array.length : stepSize);

  int[] array2 = new int[array.length];
  boolean safe = false;
  for (int i = 0; i < array.length; i++) {
     if (safe) {
        array2[i] = array[i - shiftStep];
     }
     else {
        array2[i] = array[array.length - shiftStep + i];
        safe = (i+1) - shiftStep >= 0;
     }
  }
  return array2;
}

Код работает отлично, но возможно ли достичь этого, не создавая вспомогательный массив (который является массивом 2 в приведенном выше коде)?

Спасибо!

Answer 1

Вы можете сделать это без создания как большого массива:

// void return type as it shifts in-place
private static void shiftArray(int[] array, int stepSize) {
    // TODO: Cope with negative step sizes etc
    int[] tmp = new int[stepSize];
    System.arraycopy(array, array.length - stepSize, tmp, 0, stepSize);
    System.arraycopy(array, 0, array, stepSize, array.Length - stepSize);
    System.arraycopy(tmp, 0, array, 0, stepSize);
}

Таким образом, для массива 100 000 и размера шага 10 создается массив из 10 элементов, копиипоследние 10 элементов копируют в него первые 999 990 элементов, которые будут позже, затем копируют из временного массива обратно в start массива.

Answer 2

Вы можете сделать это с помощью пары петель, но это не так просто.Использование рекурсии в этом случае проще.

public static void main(String... args) {
    for (int i = 0; i < 12; i++) {
        int[] ints = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
        rotateLeft(ints, i);
        System.out.println(Arrays.toString(ints));
    }
}

public static void rotateLeft(int[] array, int num) {
    rotateLeft(array, num, 0);
}

private static void rotateLeft(int[] array, int num, int index) {
    if (index >= array.length) return;
    int tmp = array[(index + num) % array.length];
    rotateLeft(array, num, index + 1);
    array[index] = tmp;
}

печать

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

Answer 3

Используйте не i ++, а i + = shiftSize и несколько циклов (их количество будет равно gcd для array.length и shiftSize).

Тогда вам понадобится только один тип int, поскольку буфер и время выполнения будут практически одинаковыми.

Answer 4

Это не проверено ...

public void rotateByStep(int[] array, int step) {
    step = step % array.length;
    if (step == 0) {
        return;
    }
    int pos = step;
    int tmp = array[0];
    boolean inc = array.length % step == 0;
    for (int i = 0; i < array.length; i++) {
        int tmp2 = array[pos];
        array[pos] = tmp;
        tmp = tmp2;
        pos = (pos + step) % array.length;
        if (inc && pos < step) {
            array[pos] = tmp;
            pos++;
            tmp = array[pos];
        }
    }
}

Идея, которую я пытаюсь реализовать, заключается в следующем:

• Если step не является фактором length, то увеличение индекса (pos) на step по модулю length, начиная с нуля, будет посещать каждый элемент массива один раз после length итераций.

  * * 1015

• Если step является фактором length, то индекс (с приращением, как указано выше) вернется к своей начальной точке после length / step итераций. Но если вы , затем увеличиваете на единицу, вы можете обработать цикл, начиная с 1, а затем с 2 и так далее. После length итераций мы посетим каждый элемент массива один раз.

Остальное - это просто колебание значений элементов при циклическом переборе индексов элементов ... с некоторой корректировкой при переходе к следующему циклу.

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

Answer 5

Да, это возможно, вам нужно только временно сохранить один элемент, дополнительный к массиву. В основном, что вы хотите сделать, это:

1. сохранить последний элемент в tmp var
2. сдвиг всех элементов вправо на один, начиная со второго до последнего элемента
3. sotre tmp var в качестве первого элемента
4. повторите с шага 1 в зависимости от вашего шага

Answer 6

За n-1 итераций

#include <stdio.h>

    int main(int argc, char **argv) {
        int k = 0, x = 0;
        int a[] = {-5,-4,-1,0,1,2,30,43,52,68,700,800,9999};
        int N = 0, R = 57; /*R = No of rotations*/
        int temp = 0, temp2  = 0, start = 0, iter = 0;

        x = 0;
        temp2 = a[x];

        N = sizeof(a) / sizeof(a[0]);
        for ( k = 0; k < N - 1; k++) {
            x = x + R;
            while ( x >= N ) {
                x = x - N;
            }
            temp = a[x];
            a[x] = temp2;
            temp2 = temp;
            if ( x == start ) {
                start = start + 1;
                x = x + 1;
                temp2 = a[x];
            }
            iter++;
        }
        a[start] = temp2;
        for ( k = 0; k < N; k++) {
            printf(" %d", a[k]);
        }
        printf("\n");
        printf("Done in %d iteration\n", iter);
        return 0;
    }