Schreiben Sie eine Funktion, die ein ganzzahliges Array um eine bestimmte Zahl k dreht. k Elemente vom Ende sollten zum Anfang des Arrays verschoben werden, und alle anderen Elemente sollten nach rechts verschoben werden, um den Platz zu schaffen.

Die Drehung sollte an Ort und Stelle erfolgen.

Der Algorithmus sollte nicht in mehr als O (n) ausgeführt werden, wobei n die Größe des Arrays ist.

Außerdem muss ein konstanter Speicher verwendet werden, um die Operation auszuführen.

Zum Beispiel,

Wenn das Array mit Elementen initialisiert wird, ist arr = {1, 2, 3, 4, 5, 6, 7, 8, 9}

Durch Drehen (arr, 3) werden die Elemente zu {7, 8, 9, 1, 2, 3, 4, 5, 6}.

Drehen (arr, 6) führt zu {4, 5, 6, 7, 8, 9, 1, 2, 3}

C (104)

void reverse(int* a, int* b)
{
    while (--b > a) {
        *b ^= *a;
        *a ^= *b;
        *b ^= *a;
        ++a;
    }
}

void rotate(int *arr, int s_arr, int by)
{
    reverse(arr, arr+s_arr);
    reverse(arr, arr+by);
    reverse(arr+by, arr+s_arr);
}

Minimiert:

v(int*a,int*b){while(--b>a){*b^=*a;*a^=*b;*b^=*a++;}}r(int*a,int s,int y){v(a,a+s);v(a,a+y);v(a+y,a+s);}

APL (4)

¯A⌽B

• A ist die Anzahl der zu drehenden Stellen
• B ist der Name des Arrays, das gedreht werden soll

Ich bin nicht sicher, ob APL es tatsächlich benötigt, aber in der Implementierung, die ich gesehen habe (die Interna von), würde dies Zeit proportional zu Aund konstanten Speicher benötigen .

Hier ist eine langwierige C-Version von Colins Idee.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int gcd(int a, int b) {
  int t;
  if (a < b) {
    t = b; b = a; a = t;
  }
  while (b != 0) {
    t = a%b;
    a = b;
    b = t;
  }
  return a;
}

double arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
int s_arr = sizeof(arr)/sizeof(double);

/* We assume 1 <= by < s_arr */
void rotate(double *arr, int s_arr, int by) {
  int i, j, f;
  int g = gcd(s_arr,by);
  int n = s_arr/g;
  double t_in, t_out;

  for (i=0; i<g; i++) {
    f = i;
    t_in = arr[f + s_arr - by];
    for (j=0; j<n; j++) {
      t_out = arr[f];
      arr[f] = t_in;
      f = (f + by) % s_arr;
      t_in = t_out;
    }
  }
}

void print_arr(double *arr, int s_arr) {
  int i;
  for (i=0; i<s_arr; i++) printf("%g ",arr[i]);
  puts("");
}

int main() {
  double *temp_arr = malloc(sizeof(arr));
  int i;

  for (i=1; i<s_arr; i++) {
    memcpy(temp_arr, arr, sizeof(arr));
    rotate(temp_arr, s_arr, i);
    print_arr(temp_arr, s_arr);
  }
}

C.

Ich bin mir nicht sicher, was die Kriterien sind, aber da ich Spaß mit dem Algorithmus hatte, ist hier mein Eintrag:

void rotate(int* b, int size, int shift)
{
    int *done;
    int *p;
    int i;
    int saved;
    int c;

    p = b;
    done = p;
    saved = *p;
    for (i = 0; i < size; ++i) {
        c = saved;
        p += shift;
        if (p >= b+size) p -= size;
        saved = *p;
        *p = c;
        if (p == done) {
            p += 1;
            done = p;
            saved = *p;
        }
    }
}

Ich werde es auch für ein gutes Maß Golf spielen; 126 Bytes können kürzer gemacht werden:

void r(int*b,int s,int n){int*d,*p,i,t,c;d=p=b;t=*p;for(i=0;i<s;++i){c=t;p+=n;if(p>=b+s)p-=s;t=*p;*p=c;if(p==d){d=++p;t=*p;}}}

Ich sehe hier nicht sehr viele C ++ - Lösungen, also dachte ich mir, ich würde es versuchen, da es keine Zeichen zählt.

Dies ist eine echte "In-Place" -Rotation, verwendet also 0 zusätzlichen Platz (außer technisch Swap und 3 Ints) und erfüllt, da die Schleife genau N ist, auch die O (N) -Komplexität.

template <class T, size_t N>
void rot(std::array<T,N>& x, int shift)
{
        size_t base=0;
        size_t cur=0; 
        for (int i = 0; i < N; ++i)
        {
                cur=(cur+shift)%N; // figure out where we are going
                if (cur==base)     // exact multiple so we have to hit the mods when we wrap
                {
                        cur++;
                        base++;
                }
                std::swap(x.at(base), x.at(cur)); // use x[base] as holding area
        }
}

Wenn Sie jeden der möglichen Rotationszyklen nacheinander um n ausführen (es gibt GCD (n, len (arr)) davon), benötigen Sie nur eine einzige temporäre Kopie eines Array-Elements und einige Statusvariablen. So in Python:

from fractions import gcd

def rotate(arr, n):
    total = len(arr)
    cycles = gcd(n, total)
    for start in range(0, cycles):
        cycle = [i % total for i in range(start, abs(n * total) / cycles, n)]
        stash = arr[cycle[-1]]
        for j in reversed(range(1, len(cycle))):
            arr[cycle[j]] = arr[cycle[j - 1]]
        arr[cycle[0]] = stash

C (137 Zeichen)

#include <stdio.h>

void rotate(int * array, int n, int k) {
    int todo = (1<<n+1)-1;
    int i = 0, j;
    int tmp = array[0];

    while (todo) {
        if (todo & 1<<i) {
            j = (i-k+n)%n;
            array[i] = todo & 1<<j ? array[j] : tmp;
            todo -= 1<<i;
            i = j;
        } else tmp = array[++i];
    }
}

int main() {
    int a[] = {1,2,3,4,5,6,7,8,9};
    rotate(a, 9, 4);
    for (int i=0; i<9;i++) printf("%d ", a[i]);
    printf("\n");
}

Funktion rotateauf 137 Zeichen reduziert:

void r(int*a,int n,int k){int m=(1<<n+1)-1,i=0,j,t=a[0];while(m)if(m&1<<i){j=(i-k+n)%n;a[i]=(m&1<<j)?a[j]:t;m-=1<<i;i=j;}else t=a[++i];}

Factor verfügt über einen integrierten Typ für drehbare Arrays. <circular>Dies ist also eine O (1) -Operation:

: rotate ( circ n -- )
    neg swap change-circular-start ;

IN: 1 9 [a,b] <circular> dup 6 rotate >array .
{ 4 5 6 7 8 9 1 2 3 }
IN: 1 9 [a,b] <circular> dup 3 rotate >array .
{ 7 8 9 1 2 3 4 5 6 }

Ein weniger betrügerisches Faktoräquivalent zu Ben Voigts beeindruckender C-Lösung:

: rotate ( n s -- ) 
    reverse! swap cut-slice [ reverse! ] bi@ 2drop ;

IN: 7 V{ 0 1 2 3 4 5 6 7 8 9 } [ rotate ] keep .
V{ 3 4 5 6 7 8 9 0 1 2 }

JavaScript 45

Ging sowieso zum Golf, weil ich Golf mag. Es ist maximal O (N), solange t<= Größe des Arrays ist.

function r(o,t){for(;t--;)o.unshift(o.pop())}

Um mit einem tbeliebigen Anteil in O (N) umzugehen, kann Folgendes verwendet werden (mit einem Gewicht von 58 Zeichen):

function r(o,t){for(i=t%o.length;i--;)o.unshift(o.pop())}

Wird nicht zurückgegeben, bearbeitet das Array an Ort und Stelle.

REBEL - 22

/_(( \d+)+)( \d+)/$3$1

Eingabe: k ausgedrückt als unäre Ganzzahl unter Verwendung _einer Ziffer, gefolgt von einem Leerzeichen und einem durch Leerzeichen getrennten Array von Ganzzahlen.

Ausgabe: Ein Leerzeichen, dann wird das Array gedreht.

Beispiel:

___ 1 2 3 4 5/_(( \d+)+)( \d+)/$3$1

Endzustand:

 3 4 5 1 2

Erläuterung:

Bei jeder Iteration wird eine _und ein Array [array] + taildurch ersetzt tail + [array].

Beispiel:

___ 1 2 3 4 5
__ 5 1 2 3 4
_ 4 5 1 2 3
 3 4 5 1 2

Java

public static void rotate(int[] arr, int by) {
    int n = arr.length;
    int i = 0;
    int j = 0;
    while (i < n) {
        int k = j;
        int value = arr[k];
        do {
            k = (k + by) % n;
            int tmp = arr[k];
            arr[k] = value;
            value = tmp;
            i++;
        } while (k != j);
        j++;
    }
}

Demo hier .

Minimiertes Javascript, 114 :

function rotate(e,r){n=e.length;i=0;j=0;while(i<n){k=j;v=e[k];do{k=(k+r)%n;t=e[k];e[k]=v;v=t;i++}while(k!=j);j++}}

Haskell

Dies ist tatsächlich θ (n), da die Aufteilung θ (k) und die Verbindung θ (nk) ist. Ich bin mir jedoch nicht sicher über das Gedächtnis.

rotate 0 xs = xs
rotate n xs | n >= length xs = rotate (n`mod`(length xs)) xs
            | otherwise = rotate' n xs

rotate' n xs = let (xh,xt) = splitAt n xs in xt++xh

Python 3

from fractions import gcd
def rotatelist(arr, m):
    n = len(arr)
    m = (-m) % n # Delete this line to change rotation direction
    for i0 in range(gcd(m, n)):
        temp = arr[i0]
        i, j = i0, (i0 + m) % n
        while j != i0:
            arr[i] = arr[j]
            i, j = j, (j + m) % n
        arr[i] = temp

Konstante
O (n) Zeitkomplexität des Speichers

Python

def rotate(a, n): a[:n], a[n:] = a[-n:], a[:-n] 

Python

   import copy
    def rotate(a, r):
        c=copy.copy(a);b=[]
        for i in range(len(a)-r):   b.append(a[r+i]);c.pop();return b+c

vb.net O (n) (nicht konstanter Speicher)

Function Rotate(Of T)(a() As T, r As Integer ) As T()     
  Dim p = a.Length-r
  Return a.Skip(p).Concat(a.Take(p)).ToArray
End Function

Rubin

def rotate(arr, n)
  arr.tap{ (n % arr.size).times { arr.unshift(arr.pop) } }  
end

C (118)

Wahrscheinlich war es mit einigen Spezifikationen etwas zu nachsichtig. Verwendet Speicher proportional zu shift % length. Kann sich auch in die entgegengesetzte Richtung drehen, wenn ein negativer Verschiebungswert überschritten wird.

r(int *a,int l,int s){s=s%l<0?s%l+l:s%l;int *t=malloc(4*s);memcpy(t,a+l-s,4*s);memcpy(a+s,a,4*(l-s));memcpy(a,t,4*s);}

Python 2, 57

def rotate(l,n):
 return l[len(l)-n:len(l)]+l[0:len(l)-n]

Wenn es nur so l[-n:len(l)-n]funktionieren würde, wie ich es erwarten würde. Es kehrt nur []aus irgendeinem Grund zurück.

def r(a,n): return a[n:]+a[:n]

Könnte jemand bitte prüfen, ob dies tatsächlich den Anforderungen entspricht? Ich denke schon, aber ich habe CS (noch) nicht studiert.

C ++, 136

template<int N>void rotate(int(&a)[N],int k){auto r=[](int*b,int*e){for(int t;--e>b;t=*b,*b++=*e,*e=t);};r(a,a+k);r(a+k,a+N);r(a,a+N);}

Java

Tauschen Sie die letzten k Elemente gegen die ersten k Elemente aus und drehen Sie dann die verbleibenden Elemente um k. Wenn Sie am Ende weniger als k Elemente übrig haben, drehen Sie diese um k% der verbleibenden Elemente. Ich glaube nicht, dass irgendjemand oben diesen Ansatz gewählt hat. Führt genau eine Auslagerungsoperation für jedes Element aus und erledigt alles an Ort und Stelle.

public void rotate(int[] nums, int k) {
    k = k % nums.length; // If k > n, reformulate
    rotate(nums, 0, k);
}

private void rotate(int[] nums, int start, int k) {
    if (k > 0) {
        if (nums.length - start > k) { 
            for (int i = 0; i < k; i++) {
                int end = nums.length - k + i;
                int temp = nums[start + i];
                nums[start + i] = nums[end];
                nums[end] = temp;
            }
            rotate(nums, start + k, k); 
        } else {
            rotate(nums, start, k % (nums.length - start)); 
        }
    }
}

Perl 5 , 42 Bytes

sub r{$a=pop;map{unshift@$a,pop@$a}1..pop}

Probieren Sie es online aus!

Das Unterprogramm verwendet den zu drehenden Abstand als ersten Parameter und einen Verweis auf das Array als zweiten. Die Laufzeit ist basierend auf dem Rotationsabstand konstant. Die Arraygröße hat keinen Einfluss auf die Laufzeit. Das Array wird geändert, indem ein Element von rechts entfernt und links platziert wird.