Алгоритм вращения массива за линейное время

Question

Как повернуть массив целых чисел i раз, используя функцию swap только за линейное время.

Answer 1

Вы можете сделать это за линейное время, используя помощник reverse ().

// rotate array of size=size, by n positions
void rotate(int array[], int size, int n)
{
  // reverse array[0...size-1]
  reverse(array, 0, size-1);

  // reverse A[0...n-1]
  reverse(array, 0, n-1);

  // reverse A[n...size-1]
  reverse(array, n, size-1);
}

// reverse elements in the array[pos_from ... pos_to]
void reverse(int array[], int pos_from, int pos_to)
{
   ...
}

Реализация reverse(int array[], int pos_from, int pos_to) с использованием свопов оставлена ​​в качестве упражнения для читателя. Подсказка: это можно сделать за линейное время.

Answer 2

Допустим, у нас есть функция с именем arr_reverse(arr,i,j), которая переворачивает элементы массива arr между индексами i и j, используя функцию swap.

Пример:

arr = {1,2,3,4,5} 
i = 0
j = 2

тогда функция вернется:

{3,2,1,4,5} 
 ^^^^^

Реализация этой функции проста и является O(N).

Теперь давайте использовать эту функцию при вращении массива.

arr     = {1,2,3,4,5} // input array
k       = 2 // amount of right rotation
result  = {4,5,1,2,3} // expected result 
l       = 5 // length of array.

Step 1: Call arr_reverse(arr,l-k,l-1) which is arr_reverse(arr,3,4)
we get {1,2,3,5,4} 
              ^^^

Step 2: Call arr_reverse(arr,0,l-k-1) which is arr_reverse(arr,0,2)
we get {3,2,1,5,4}
        ^^^^^     

Step 3: Call arr_reverse(arr,0,l-1) which is arr_reverse(arr,0,4)
we get {4,5,1,2,3} 
        ^^^^^^^^^

Весь процесс использует arr_reverse 3 раза, делая его O(N)

Answer 3

Вот лучшее решение, отличающееся от других.Это включает в себя меньше перестановок массивов, чем другие.Python:

import fractions
# rotates an array in-place i positions to the left, in linear time
def rotate(arr,i):
    n = len(arr)
    reps = fractions.gcd(n,i)
    swaps = n / reps
    for start in xrange(reps):
        ix = start
        tmp = arr[ix]
        for s in xrange(swaps-1):
            previx = ix
            ix = (ix + i) % n
            arr[previx] = arr[ix]
        arr[ix] = tmp
    return arr

Answer 4

Используя линейное время O (2N + m) и постоянное пространство O (4).m = GCD (n, p)

Это на 50% быстрее, чем подход подкачки, потому что подкачка требует записи O (N) раз во временную.

http://www.eis.mdx.ac.uk/staffpages/r_bornat/oldteaching/I2A/slides%209%20circshift.pdf

for (m=0, count=0; count!=n; m++) {
    type t=A[m];
    for (i=m, j=m+p; j!=m; i=j, j = j+p<n ? j+p : j+p-n, count++)
        A[i]=A[j];
    A[i]=t; count++;
}

Answer 5

public int[] shift(int[] A, int K) {
    int N = A.length;
    if (N == 0)
        return A;
    int mid =  -K % N;
    if (mid < 0)
        mid += N;
    if (mid == 0)
        return A;

    reverseSubArray(A, 0 , mid - 1);

    reverseSubArray(A, mid , N - 1);

    reverseSubArray(A, 0 , N - 1);

    return A;
}

private void reverseSubArray(int[] A, int start , int end){
    int i = 0;
    int tmp;
    while (i < (end - start + 1) / 2) {
        tmp = A[i + start];
        A[i + start] = A[end - i];
        A[end - i] = tmp;
        i++;
    }

}

Описание руки Дуга Макилроя

Answer 6

Лучше использовать прямую и простую функцию, сложность N:

int rotate(int* a,int DIM,int rn,int* b) {
    int i; //counter 
    for(i=0;i<DIM;i++){ // looping through the array
        b[(i+rn)%len]=a[i]; // copying the values in the b array=a shifted with rn(+ for right or - for left shifting
}

Answer 7

Наивная реализация псевдокода:

for (n = 0; n < i; n++) {
    for (j = array.length-1; j > n; j--)
        swap(j, j-1)
}

Неоднократно перемещает последний элемент вперед, останавливаясь, прежде чем он перемещает что-либо ранее перемещенное вперед

Answer 8

вот мой ответ с использованием js, надеюсь, это поможет, где k - это число оборотов, которые вы хотите выполнить

 var arrayRoatate=function(array,k){
    for(;k>0;k--) {
     var nextElementValue=undefined;
        for (var i = 0; i < array.length; i=i+2) {
            var nextElement = i + 1;
            if (nextElement >= array.length)
                nextElement = nextElement - array.length;
            var tmp=array[i];
            if(nextElementValue!==undefined)
                array[i]=nextElementValue
            nextElementValue=array[nextElement];
            array[nextElement]=tmp;

        }
    }
return array;

Answer 9

public static String rotateKTimes(String str,int k){
    int n = str.length();

    //java substring has O(n) complexity
    return str.substring(n-k) + str.substring(0,n-k);
}

Answer 10

O(1) метод выполнения этого в python:

class OffsetList(list):
    __slots__ = 'offset'
    def __init__(self, init=[], offset=-1):
        super(OffsetList, self).__init__(init)
        self.offset = offset
    def __getitem__(self, key):
        return super(OffsetList, self).__getitem__(key + self.offset)
    def __setitem__(self, key, value):
        return super(OffsetList, self).__setitem__(key + self.offset, value)
    def __delitem__(self, key):
        return super(OffsetList, self).__delitem__(key + self.offset)
    def index(self, *args):
        return super(OffsetList, self).index(*args) - self.offset

Это основано на ответе об использовании списка на основе 1 в python .

Это имеет небольшой недостаток: если вы попытаетесь проиндексировать элемент за пределами списка, он вернет элементы с начала (нового), а отрицательные значения меньше размера, за вычетом смещения, работать не будет.