Algoritmo per ruotare una matrice in tempo lineare

Come ruotare un array intero di volte in volta utilizzando la funzione di swap solo in tempo lineare.

Puoi farlo in tempo lineare usando un helper 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) { ... } 

L’implementazione reverse(int array[], int pos_from, int pos_to) utilizzando gli swap viene lasciata come esercizio per il lettore. Suggerimento: questo può essere fatto in tempo lineare.

Diciamo che abbiamo una funzione chiamata arr_reverse(arr,i,j) che inverte gli elementi dell’array arr tra indice i e j usando la funzione swap .

Esempio:

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

quindi la funzione restituirà:

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

L’implementazione di questa funzione è semplice ed è O(N) .

Ora usiamo questa funzione per far ruotare la matrice.

 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,lk,l-1) which is arr_reverse(arr,3,4) we get {1,2,3,5,4} ^^^ Step 2: Call arr_reverse(arr,0,lk-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} ^^^^^^^^^ 

L’intero processo usa arr_reverse 3 volte, rendendolo O(N)

Ecco una soluzione migliore, di natura diversa dalle altre. Implica meno scambi di array rispetto agli altri. Pitone:

 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 

Utilizzo del tempo lineare O (2N + m) e dello spazio costante O (4). m = GCD (n, p)

È fino al 50% più veloce rispetto all’approccio di swapping, perché lo swapping richiede di scrivere O (N) volte in modo temporaneo.

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 

un’implementazione pseudocodifica ingenua:

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

Sposta ripetutamente l’ultimo elemento in avanti, fermandosi prima di spostare qualsiasi cosa precedentemente spostata in avanti

Meglio usare una funzione diretta e semplice, la complessità N:

 int rotate(int* a,int DIM,int rn,int* b) { int i; //counter for(i=0;i 

perché solo funzione di scambio?

O (n) nel tempo e nello spazio:

 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 
 /* 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  #include  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 */ 

usando solo lo swap, di seguito è una implementazione in C ++

 template void rotate_array(std::vector *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)); } } } 

Puoi leggere ulteriori informazioni al riguardo su http://pointer-overloading.blogspot.in/2013/09/algorithms-rotating-one-dimensional.html

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

}

Ecco un piccolo frammento che funziona in O (n), scritto in JavaScript. Il keyconcept è che devi sempre lavorare con l’object sostituito.

 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)) 

Un metodo O(1) per realizzare questo, in 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 

Questo è basato su questa risposta sull’utilizzo di un elenco basato su 1 in python .

Questo ha il leggero problema che se si tenta di indicizzare un object al termine dell’elenco, esso restituirà gli elementi dal (nuovo) inizio e gli indici negativi inferiori alla dimensione meno lo scostamento non funzionerà.

ecco la mia risposta usando js spero che questo aiuti dove k è il numero delle rotazioni che vuoi preformare

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

Descrizione di Handwaving di Doug McIlroy

 /* * 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]); } } } 

Per rotazione destra circolare.

 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()]); } } 
 public static String rotateKTimes(String str,int k){ int n = str.length(); //java substring has O(n) complexity return str.substring(nk) + str.substring(0,nk); } 
 Simple Solution in O(n) time and using O(1) space: for eg 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