Как выполнить сдвиг влево на круговом массиве целых?

Question

Существует ли существующий метод, который выполняет сдвиг влево на круговом массиве целых чисел?

В частности, учитывая массив из 4 элементов {1,2,3,4} и величину сдвига 2, я хотел бы метод, которыйсдвигает первые две буквы в конец массива, делая его таким образом: {3,4,1,2}.

Будет ли этот алгоритм работать для смещения кругового массива на единицу?

algShiftByOne(Array)
{
  temp=array[0];
  i=1
  while(i < Array.length - 1) // Loop from 1 up to array.length == last index
  {
    // If there is no exception i assume it copies value from
    // initial array starting from 1 up to array.length
    Array[i - 1] = Array[i];
    i++;
  }
 Array[Array.length]=temp;
}

Answer 1

Вот мой пример ... (вот демоверсия ideone.com )

import java.util.Arrays;

public class Test {

    public static void circularShiftLeft(int[] arr) {
        if (arr.length == 0)
            return;

        int first = arr[0];
        System.arraycopy(arr, 1, arr, 0, arr.length - 1);
        arr[arr.length - 1] = first;
    }

    public static void main(String[] arg) {
        int[] arr = { 1, 2, 3, 4 };
        System.out.println(Arrays.toString(arr));
        circularShiftLeft(arr);
        System.out.println(Arrays.toString(arr));
    }
}

Answer 2

У меня был этот вопрос на собеседовании.Простое на месте (и несколько интуитивно понятное) решение O (2n) для вращения m состоит в том, чтобы взять массив, повернуть его вспять, затем обратить вспять подмассивы [0, m] и (m, n]. Мое решение, хотя и немного менее очевидное, находится на месте и O (n). В основном идея заключается в том, что вы поворачиваете элементы вперед на один элемент, и в конечном итоге вы пройдете через все элементы. Выгода заключается в том, что массив кратен расстоянию, в котором находится GCDПриходит следующее. Поворот вправо, поворот влево - читателю в качестве упражнения:

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

public static void rotate(int[] arr, int dist){
    int tmp, tmp2, gcd = GCD(arr.length, dist);
    for(int off=0;off<gcd;off++){
        tmp = arr[off];
        for(int i=0,idx=off;i<arr.length/gcd;idx=(idx+dist)%arr.length,i++){
            tmp2 = arr[(idx+dist)%arr.length];
            arr[(idx+dist)%arr.length] = tmp;
            tmp = tmp2;
        }
    }
}

public static int GCD(int a, int b) {
   if (b==0) return a;
   return GCD(b,a%b);
}

Answer 3

public static void shift(int[] arr, int offs) {
    // e.g. arr = 1,2,3,4,5,6,7,8,9; offs = 3
    offs %= arr.length;
    offs = offs < 0 ? arr.length + offs : offs;

    if (offs > 0) {
        // reverse whole array (arr = 9,8,7,6,5,4,3,2,1)
        for (int i = 0, j = arr.length - 1; i < j; i++, j--)
            swap(arr, i, j);
        // reverse left part (arr = 7,8,9,6,5,4,3,2,1)
        for (int i = 0, j = offs - 1; i < j; i++, j--)
            swap(arr, i, j);
        // reverse right part (arr = 7,8,9,1,2,3,4,5,6)
        for (int i = offs, j = arr.length - 1; i < j; i++, j--)
            swap(arr, i, j);
    }
}

private static void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

Answer 4

Это сместит массив на один влево.

int[] a = new int[] { 1, 2, 3, 4, 5 };
int[] b = new int[a.length];
System.arraycopy(a, 1, b, 0, a.length - 1);
b[a.length - 1] = a[0];
// b = {2,3,4,5,1}
// edit
a = b;

Answer 5

Вот некоторый псевдокод, чтобы делать то, что вы хотите.

Array shift(Array a, int shiftLength) {
    Array b;

    for(i = shiftLength; i < a.size(); i++)
        b.add(a.at(i));

    for(i = 0; i < shiftLength; i++)
        b.add(a.at(i));

    return b;
}

Answer 6

Почему бы вам не использовать круговой (дважды) связанный список? В этом случае вам нужно всего лишь изменить «указатель начала».

Answer 7

Предполагая, что вы хотите сдвинуться на n:

1. Скопируйте первые n элементов в массив с именем, например, tempNumbers
2. Для каждого элемента от n до последнего сдвиньте его влево на n
3. Скопировать элементы из tempNumbers в конец исходного массива