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

Question

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

Answer 1

Вот небольшой фрагмент, который работает на O (n), написанный на JavaScript.Суть в том, что вы всегда должны работать с замененным элементом.

function swap(arr, a, v) {
    var old = arr[a];
    arr[a] = v;
    return old;
}

function rotate(arr, n) {
    var length = arr.length;
    n = n % length;
    if(!n) return arr;

    for(var cnt = 0, 
            index = 0,
            value = arr[index],
            startIndex = index; 
        cnt < length; 
        cnt++) {

        // Calc next index
        var nextIndex = mapIndex(index, n, length);

        // Swap value with next
        value = swap(arr, nextIndex, value)

        if(nextIndex == startIndex) {
            startIndex = index = mapIndex(index, 1, length);
            value = arr[index];
        } else {
            index = nextIndex;
        }
    }

    return arr;
}

function mapIndex(index, n, length) {
    return (index - n + length) % length;
}

console.log(rotate([1,2,3,4,5,6,7,8,9], 5))
console.log(rotate([1,2,3,4,5,6], 2))

Answer 2

почему только функция подкачки?

O (n) во времени и пространстве:

var rotateCount = 1;
var arr = new Array(1,2,3,4,5,6,7,8,9,10);

tmp = new Array(arr.length);
for (var i = 0; i<arr.length; i++)
    tmp[(i+rotateCount)%arr.length]=arr[i];
arr = tmp;

alert(arr);

Answer 3

Мое решение с Java

static int[] rotLeft(int[] a, int d) {
    for (int i = 0; i < d; i++) {
        oneRotation(a);
    }
    return a;
}

static void oneRotation(int[] a) {
    int firstElement = a[0];
    for (int i = 0; i < a.length - 1; i++) {
        a[i] = a[i + 1];
    }
    a[a.length - 1] = firstElement;
}

Answer 4

/* Q: How can we shift/rotate an array in place?
A: "in place" means O(1) space complexity, so we need to do some trick
 */

#include <iostream>
#include <algorithm>
using namespace std;

void ArrayRotate(int a[], int n, int k)
{
    if (n < 1 || k % n == 0 ) return;

    k %= n;
    if (k < 0) k += n;

    reverse(a, a+k);
    reverse(a+k, a+n);
    reverse(a, a+n);
}

void PrintArray(int a[], int n)
{
    for ( int i = 0 ; i < n; ++i)
        cout << a[i] << " ";
    cout << endl;
}

int main()
{
    int a[] = { 1, 2 , 3, 4, 5 };
    int n = sizeof(a)/sizeof (a[0]);

    PrintArray(a, n);
    ArrayRotate(a, n, 2);
    PrintArray(a, n);

    return 0;
}
/* Output:
1 2 3 4 5
3 4 5 1 2
 */

Answer 5

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package rotateinlineartime;

/**
 *
 * @author Sunshine
 */
public class Rotator {

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

        printArray(a);
    }

    void printArray(int a[]) {
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }
    }
}

Answer 6

Simple Solution in O(n) time and using O(1) space:
for e.g 1,2,3,4,5,6,7
rotating 2 times 
start with index 2, store a[0] as last
Iteration 1: 1,2,1,4,3,6,5 (1-->3-->5-->7)
Iteration 2: 1,7,1,2,3,4,5 (2-->4-->6)
replace 1 with 6 (last value).

public int[] roatateArray(int[] a,int k)
{
    int last = a[0];
    int start = k;
    for(int j=0;j<k;j++) {
    for(int i=start;i<a.length;i+=k)
    {
        int tmp=a[i];
        a[i]=last;
        last=tmp;
    }
    start--;
    if (start<=0) break;
    }
    a[0]=last;
    return a;
}

Answer 7

Для кругового вращения вправо.

public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    int n = scan.nextInt();
    int k = scan.nextInt() % n;
    int q = scan.nextInt();
    int arr[] = new int[n];

    for (int i = 0; i < n; i++) 
    {
        int a = i + k;
        int pos = (a < n) ? a : a - n;
        arr[pos] = scan.nextInt();
    }
    for (int j = 0; j < q; j++) 
    {
        System.out.println(arr[scan.nextInt()]);
    }
}

Answer 8

с использованием только подкачки, ниже приведена реализация C ++

template<class T>
void rotate_array(std::vector<T> *array, int i) {
  int n = array->size();
  i = i % n;
  int gcd_n_i = gcd(i, n);
  for (int j = 0; j < gcd_n_i; j++) {
    T first_element = array->at(j);
    for (int k = j; (k + i) % n != j; k = (k + i) % n) {
      std::swap(array->at(k), array->at((k + i) % n));
    }
  }
}

Подробнее об этом можно прочитать по адресу http://pointer -overloading.blogspot.in / 2013/09 / алгоритмы-вращающегося-одномерного.html

Answer 9

Этот алгоритм (не более) len(array)-1 меняет местами и работает как с положительными (справа), так и с отрицательными (слева) значениями поворота.Массив изменяется на месте.
Не требует вычисления GCD, в отличие от других подобных методов.

(Python 3)

def rotate(array,amount):
    if amount<0:
        amount+=len(array)
    a=0
    b=0
    for _ in range(len(array)-1):
        b=(b+amount) % len(array)
        if b==a:
            a+=1
            b=a
        if b!=a:
            array[a],array[b] = array[b],array[a] #swap array[a],array[b]
    return array

Когда одного цикла недостаточно (если он возвращается к началу до достижения каждого индекса), начинайте новый цикл со следующего индекса.

Примечание: вращающиеся элементы a, b, c, d, ...можно сделать, используя
swap a,b swap a,c swap a,d ...

Answer 10

void reverse_array(int a[], int start, int end){

    while(start < end){     
            int temp =  a[start];
            a[start] = a[end];
            a[end] = temp;
            start++;
            end--;
    }

}

void rotate_array(int a[], int pivot, int len){
    int i;
    /*Reverse the whole array */
    reverse_array(a, 0, len);

    /* Reverse from 0 to pivot and pivot to end */
    reverse_array(a,0, pivot);
    reverse_array(a,pivot+1,len);

}