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

Question

Я пытаюсь сделать круговое смещение влево массива на n позиций, используя только один одномерный массив. Я могу сделать это в двух массивах, но я не понял, как это сделать, используя один. Пожалуйста, дайте ваши предложения

Answer 1

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

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;
    }
}

Answer 2

Я бы сдвинул его по 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() высоко оптимизирован.

Answer 3

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

• Обратный массив от 0 до n (число OfPositions) позиций
• Обратный массив от 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]

Answer 4

Я верю, что 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-й метод. надеюсь, это поможет

Answer 5

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

Answer 6

Версия 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();
  }
}

Answer 7

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

Answer 8

Ниже я реализовал пример решения для сдвига влево или вправо массива на 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);
    }
} 

Я закомментировал правую смену.

Answer 9

for (int i = 0; i < n; i++)
    array[array.length - n + i] = array[i];
for (int i = 0; i < array.length - n; i++)
    array[i] = array[i + n];

Answer 10

Может быть, старый пост.. но здесь вы мое решение (где 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;
}

Answer 11

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

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 массив. Виноват. Я оставлю свой ответ на всякий случай, если он кому-то поможет.

Answer 12

Оформить заказ по этой ссылке:

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

circularShiftToLeftInPlace

Answer 13

Я знаю, что это старый пост, однако вот оптимальное решение за O(n): каждый элемент перемещается ровно один раз, и дополнительное пространство не требуется. Это очень похоже на решение, предложенное @SomeStrangeUser, но не требует вычисления gcd.

      public static void shiftArray(int[] A, int k) {
    if (A.length == 0) {
        return;
    }
    k = k % A.length;
    k = (k + A.length) % A.length; // ensure k is positive
    if (k == 0) {
        return;
    }
    int i = 0, i0 = 0;
    int x = A[0];
    for (int u = 0; u < A.length; u++) { // count number of shifted elements
        int j = (i - k + A.length) % A.length; // ensure modulo is positive
        if (j == i0) { // end of a (sub-)cycle, advance to next one
            A[i] = x;
            x = A[i = ++i0];
        } else {
            A[i] = A[j];
            i = j;
        }
    }
}

Answer 14

      import java.util.Scanner;

public class ArrayMoveByGivenSize {

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        
        int[] A = new int[] {100,200,300,400,500,600};
        //movement = 2
        //output {500,600,100,200,300,400}

        System.out.println("Please enter the movement size");
        int s;
        Scanner sc = new Scanner(System.in);
        s= sc.nextInt();
        System.out.println(s);
        int[] X = new int[A.length];
        for (int i=0;i<A.length;i++)
        {
            if((i+s)<A.length)
            {
                X[i+s]=A[i];
            }
            else
            {
                X[(i+s) - A.length]=A[i] ;  
            }
            
        }
        for(int i =0;i<X.length ; i++)
        System.out.println(X[i]);
        
    }
}

Answer 15

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

    // 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;
    }
}