круговой сдвиг массива влево на n позиций в java

На самом деле для этого есть хитрый алгоритм. Мы будем использовать A для обозначения массива, N для обозначения размера массива и n для обозначения количества позиций для сдвига. После сдвига вы хотели бы, чтобы элемент i-th переместился в позицию ((i + n) mod N)-th, поэтому мы можем определить новые позиции с помощью следующего сопоставления:

f(j) := (j + n) mod N  (j = 0,...,N - 1)

Общая идея этого алгоритма такова: мы не хотим перемещать элементы больше, чем это необходимо, поэтому в идеале мы хотели бы просто поместить каждый элемент в правильное (смещенное) положение с первой попытки. Скажем, мы начинаем с элемента в позиции i. Что мы хотим сделать, так это переместить элемент с позиции i в позицию f(i), но тогда мы перезапишем элемент в этой позиции, поэтому нам нужно сначала сохранить элемент в позиции f(i), а затем выполнить сдвиг. Как только мы сдвинули первый элемент, нам нужно выбрать другой элемент для сдвига. Поскольку мы хотим сэкономить место, очевидным кандидатом является только что сохраненный нами элемент (элемент, который находился в позиции f(i)). Как и раньше, мы сохраняем элемент в позиции f(f(i)), а затем копируем сохраненный элемент в эту позицию. Мы продолжаем повторять этот процесс (проходя позиции i, f(i), f(f(i)), f(f(f(i))), ...), пока не достигнем элемента, который мы уже сдвинули (что мы гарантированно сделаем, поскольку позиций конечное количество). Если мы прошли через все элементы, то мы закончили, если нет, то мы выбираем другой элемент (который еще не был сдвинут), скажем, в позиции j, и повторяем процедуру (проходя j, f(j), f(f(j)), f(f(f(j))), ...). Вот и все. Но прежде чем мы сможем реализовать такой алгоритм или даже прежде, чем мы решим, действительно ли это хороший алгоритм, нам нужно ответить на несколько вопросов:

1. Скажем, мы перебираем позиции i, f(i), f(f(i)), .... Как мы можем сказать, что достигли позиции, которая уже была сдвинута? Нужно ли нам сохранять каждую пройденную позицию? Если да, то это означает, что нам нужно хранить массив размера N (чтобы покрыть все позиции), и нам также нужно выполнять поиск каждый раз, когда мы сдвигаем элемент. Это сделало бы алгоритм ужасно неэффективным. К счастью, в этом нет необходимости, так как последовательность i, f(i), f(f(i)), ... должна обернуться вокруг самой себя в позиции i, поэтому нам нужно только подождать, пока мы не достигнем этой позиции. Мы можем доказать это утверждение следующим образом: предположим, что первый повторяющийся элемент, который мы встречаем, не является i. Тогда у нас должно быть 2 разных элемента, которые при смещении окажутся в одном и том же положении - противоречие.

2. Скажем, мы закончили i, f(i), f(f(i)), ..., но остались элементы, которые остались несмещенными (мы можем сказать, подсчитав, сколько элементов мы сдвинули). Как нам теперь найти позицию j, содержащую такой элемент? А также, как только мы закончили эту вторую итерацию (проходя через j, f(j), f(f(j)), ...), как нам найти третью позицию k с несмещенным элементом? и т. д. Это также может означать, что нам нужно сохранить массив для учета используемых используемых \ неиспользуемых элементов и выполнять поиск каждый раз, когда нам нужно найти неиспользуемый элемент. Однако мы снова можем расслабиться, поскольку, как мы скоро покажем, все начальные позиции (которые мы обозначили i, j и k) являются смежными. Это означает, что если мы начнем с позиции i, мы затем выберем i + 1, а затем i + 2 и так далее…

3. могут ли последовательности i, f(i), f(f(i)), ... и j, f(j), f(f(j)), ... (где i и j разные) содержать общие элементы? Если они это сделают, это будет означать, что алгоритм бесполезен, поскольку он может сдвинуть один и тот же элемент дважды, что приведет к тому, что он окажется в неправильном положении. Тогда ответ (конечно) заключается в том, что они не могут содержать общие элементы. И мы покажем почему.

Обозначимd := gcd(N, n). Для каждого из целых чисел: i = 0,...,d - 1 мы определяем следующий набор:

S(i) := { kd + i | k = 0,...,N/d - 1}

Легко видеть, что множества S(0),...,S(d - 1) вместе покрывают множество {0,...,N - 1}. Мы также наблюдаем, что при делении элемента в наборе S(i) на d у нас остается остаток i, а при делении элемента из другого набора S(j) на d мы получаем другой остаток (j). Таким образом, никакие два множества не содержат общего элемента. При этом мы установили, что наборы S(0),...,S(d - 1) образуют раздел {0,...,N - 1}

Теперь для каждого i = 0,...,d - 1 мы определим набор T(i) как i, f(i), f(f(i)), .... По определению f мы можем записать T(i) следующим образом:

T(i) = {(kn + i) mod N | k is an integer}

Заметим, что если x является элементом T(i), то мы можем написать для некоторого k:

x = (kn + i) mod N = (k(n/d)d + i) mod N

Обозначим z := k(n/d) mod N/d, тогда, умножив на d, получим:

kn mod N = zd

и, следовательно:

x = (kn + i) mod N = zd + i

Таким образом, x также находится в S(i). Точно так же, если мы возьмем некоторое y из S(i), мы заметим, что для некоторого k:

y = kd + i

Поскольку gcd(n/d, N/d) = 1 существует q такое, что q(n/d) mod N/d = 1 (модульное обратное), мы можем написать (умножая на kd):

kd = kqn mod N

и, следовательно:

y = kd + i = ((kq)n + i) mod N

Таким образом, y также находится в T(i). Делаем вывод, что T(i) = S(i). Из этого факта мы можем легко показать наши предыдущие утверждения. Во-первых, поскольку наборы образуют раздел {0,...,N - 1}, выполняется третье утверждение (никакие две последовательности не содержат общего элемента). Во-вторых, по определению множеств S(i) мы можем взять любую группу d смежных элементов в {0,...N - 1}, и каждый из них будет помещен в другое множество. Это удовлетворяет второму утверждению.

Это означает, что мы можем повернуть все элементы в позиции 0, d, 2d, ..., (N/d - 1)d, просто заменив элемент в позиции n mod N на элемент в позиции 0, элемент в позиции 2n mod N на элемент в позиции n mod N и т. д. … пока мы не вернемся к элементу в позиции 0 (что, как мы уверены, произойдет). Вот пример псевдокода:

temp <- A[0]
j <- N - (n mod N)
while j != 0 do
    A[(j + n) mod N] <- A[j];
    j <- (j - n) mod N
A[n mod N] <- temp;

Это охватывает весь набор S(0). Чтобы покрыть остальные наборы, а именно S(1), … ,S(d-1), мы просто пройдемся по каждому набору так же, как и для первого:

for i <- 0 to d - 1
    temp <- A[i]
    j <- N - ((n - i) mod N)
    while j != i do
        A[(j + n) mod N] <- A[j];
        j <- (j - n) mod N
    A[(i + n) mod N] <- temp;

Обратите внимание, что хотя у нас есть два вложенных цикла, каждый элемент перемещается ровно один раз, и мы используем O(1) пробела. Пример реализации на Java:

public static int gcd(int a, int b) {
    while(b != 0) {
        int c = a;
        a = b;
        b = c % a;
    }
    return a;
}

public static void shift_array(int[] A, int n) {
    int N = A.length;
    n %= N;
    if(n < 0)
        n = N + n;
    int d = gcd(N, n);
    for(int i = 0; i < d; i++) {
        int temp = A[i];
        for(int j = i - n + N; j != i; j = (j - n + N) % N)
            A[(j + n) % N] = A[j];
        A[i + n] = temp;
    }
}

Я бы сдвигал его на 1 элемент за раз, используя одну временную переменную для удержания элемента при перемещении элементов на 1 место вдоль каждого. Затем я повторил бы это n раз, чтобы получить n смен.

public static void main( String[] args ) {
    int[] array = {1,2,3,4,5,6,7,8};
    leftShift( array, 3);
    System.out.println( Arrays.toString( array));
}

public static void leftShift(int[] array, int n) {
    for (int shift = 0; shift < n; shift++) {
        int first = array[0];
        System.arraycopy( array, 1, array, 0, array.length - 1 );
        array[array.length - 1] = first;
    }
}

Вывод:

[4, 5, 6, 7, 8, 1, 2, 3]

Не слишком неэффективно, так как System.arraycopy() оптимизирован.

Вот очень простой алгоритм с O(1) пробелом в O(n)
Алгоритм

• Перевернуть массив с 0 на n (numberOfPositions) позиций
• Перевернуть массив с n+1 на длину массива - 1 позицию
• Перевернуть весь массив от 0 до длины - 1 позиция

 public class ArrayRotator {

 private final int[] target;
 private final int length;

 public ArrayRotator(int[] seed) {
    this.target = seed;
    this.length = seed.length;
 }

 public void rotateInline(int numberOfPositions) {
    reverse(0, numberOfPositions);
    reverse(numberOfPositions + 1, length-1);       
    reverse(0, length-1);
 }

 private void reverse(int start, int end) {
    for (int i = start; i <= (start + end)/2; i++) {
        swap(i, start + end - i);
    }
 }

 private void swap(int first, int second) {
    int temp = this.target[second];
    this.target[second] = this.target[first];
    this.target[first] = temp;
 }
}

Например, предположим, что массив равен [1,2,3,4], а n равен 2
После первого шага вы получите [2,1,3,4]
После второго шага вы в итоге получится [2,1,4,3]
После третьего шага вы получите [3,4,1,2]

Вы можете сдвинуть данные, повторяя и копируя, это будет O (n). Альтернативный подход заключается в создании реализации List, которая обертывает ваш массив и предоставляет его как циклический сдвиг. Это имело то преимущество, что фактическое смещение выполняется лениво, когда выполняется get или итерация.

Другой альтернативой может быть создание собственной структуры, включающей в себя массив и индекс виртуального нуля.

Я верю, что System.arraycopy на самом деле просто возьмет все ваши данные из одного массива и поместит их в другой массив той же длины, только что сдвинутый.

В любом случае, думать об этой проблеме — довольно интересная задача. Единственное решение, о котором я мог думать прямо сейчас, это гадить по одному. Без использования другого массива это будет выглядеть так:

for(int i = 0; i < shift;i++)
        {
            tmp = array[0];
            for(int j = 0;j<array.length-1;j++)
                array[j]=array[j+1];
            array[array.length-1]=tmp;
        }

для массивов более 30 элементов более эффективно использовать это:

for (int i = 0; i < shift; i++) {
            tmp = array[0];
            System.arraycopy( array, 1, array, 0, array.length - 1 );
            array[array.length - 1] = tmp;
        }

Но для больших массивов и больших сдвигов, близких к размеру массива, а также для коротких массивов и малых сдвигов этот метод выигрывает гонку:

    int[] array2 = new int[shift];
    for (int i = 0; i < shift; i++)
    {
        array2[i] = array[i];
    }
    System.arraycopy(array, shift, array, 0, array.length - shift);
    for (int i = array.length - shift; i < array.length; i++)
    {
        array[i] = array2[shift + i - array.length];
    }

Я проверил это с несколькими размерами массива и сдвигами Вот результаты для

    int[] array = new int[100000];
    int shift = 99999;

в наносекундах: 1-й метод: 5663109208 2-й метод: 4047735536 3-й метод: 6085690 Поэтому вам действительно следует использовать 3-й метод. надеюсь, это поможет

Версия Java 8:

public class Sample {
   public static void main(String[] args) {
     int[] answer = solution(new int[] {1,2,3,4}, 2);
     Arrays.stream(answer).forEach(System.out::print);
   }

   public static int[] solution(int[] A, int K) {
     List<Integer> numbers = 
     IntStream.of(A).boxed().collect(Collectors.toList());
     Collections.rotate(numbers, K);
     return numbers.stream().mapToInt(n -> n).toArray();
  }
}

Проверьте эту ссылку github:

https://github.com/techpanja/interviewproblems/blob/master/src/arrays/circularshiftintarray/CircularShiftArray.java

круговойShiftToLeftInPlace

Может быть, старый пост ... но вот мое решение (где A, очевидно, это массив, а K количество позиций).

public int[] solution(int[] A, int K){
    int[] result = new int[A.length];

    for (int i = 0; i<A.length; i++){
        result[(i+K)%A.length] = A[i];
    }
    return result;
}

Ниже я реализовал пример решения для сдвига влево или вправо массива на n элементов.

class RotateArrayByN {

    public void leftRotate(int arr[], int d, int n)
    {
        for (int i = 0; i < d; i++)
            leftRotatebyOne(arr, n);
    }

    public void rightRotate(int[] arr,int d, int n){
        for(int i=0;i<d;i++)
            rightRotatebyOne(arr,n);
    }

    public void leftRotatebyOne(int arr[], int n)
    {
        int i, temp;
        temp = arr[0];
        for (i = 0; i < n - 1; i++)
            arr[i] = arr[i + 1];
        arr[i] = temp;
    }

    public void rightRotatebyOne(int[] arr,int n){

        int temp=arr[n-1];
        for (int i=n-1;i>0;i--) {
            arr[i] = arr[i - 1];
        }
        arr[0]=temp;

    }

  public void printArray(int arr[], int n)
    {
        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");

        System.out.println();
    }


    public static void main(String[] args)
    {
        RotateArrayByN rotate = new RotateArrayByN();
        int arr[] = { 1, 2, 3, 4, 5, 6, 7 };
        System.out.println("Left Rotate");
        rotate.leftRotate(arr, 2, 7);
        rotate.printArray(arr, 7);

       //System.out.println("Right Rotate");
        //rotate.rightRotate(arr,2,7);
       // rotate.printArray(arr,7);
    }
} 

Я закомментировал правый сдвиг.

Я знаю, что это старый пост, но я нигде не видел его, поэтому:

d — это количество позиций, на которые мы хотим сдвинуться влево.

    int[] array = {1,2,3,4,5,6,7,8};
    int length = array.length;
    int d = 3;
    int[] ans = new int[length];        

    for (int i = 0; i < length; i++){
        ans[i] = array[(i + d)%length];
    }
    System.out.println(Arrays.toString(ans));

Будет выведено: [4, 5, 6, 7, 8, 1, 2, 3]

Вы можете увидеть код в действии здесь: http://tpcg.io/8cS6GIKI

Отредактировано: Неважно... Я не умею читать. Я только что видел, что OP запрашивает только 1 массив. Виноват. Я оставлю свой ответ на всякий случай, если он может кому-то помочь.

Как насчет этого?

    // Left shift the array in O(n) with O(1) space.

public static void leftShift(int[] array, int n) {
    int temp;
    int len = array.length;
    for (int i = 0; i < n; i++) {
        temp = array[len - n + i];
        array[len - n + i] = array[i];
        array[i] = array[n + i];
        array[n + i] = temp;
    }
}