Putar Array Integer dengan algoritma O (n) [ditutup]

10

Tulis fungsi yang memutar array integer dengan angka yang diberikan k. elemen k dari akhir harus pindah ke awal array, dan semua elemen lainnya harus pindah ke kanan untuk membuat spasi.

Rotasi harus dilakukan di tempat.

Algoritma tidak boleh berjalan lebih dari O (n), di mana n adalah ukuran array.

Memori konstan juga harus digunakan untuk melakukan operasi.

Sebagai contoh,

jika array diinisialisasi dengan elemen arr = {1, 2, 3, 4, 5, 6, 7, 8, 9}

rotate (arr, 3) akan menghasilkan elemen menjadi {7, 8, 9, 1, 2, 3, 4, 5, 6}

rotate (arr, 6) akan menghasilkan {4, 5, 6, 7, 8, 9, 1, 2, 3}

mikrobia
sumber
1
Apa yang dimaksud dengan memori konstan di sini? Tentunya membutuhkan setidaknya O (n) memori minimal untuk menyimpan array yang sedang diproses sehingga O (1) penggunaan memori menjadi tidak mungkin.
Ad Hoc Garf Hunter
2
Saya memberikan suara untuk menutup pertanyaan ini sebagai di luar topik karena pertanyaan tanpa kriteria pemenang utama yang obyektif adalah di luar topik, karena mereka membuat mustahil untuk memutuskan secara tak terbantahkan entri mana yang akan menang. Sama sekali tidak ada alasan bahwa ini harus menjadi kontes popularitas.
James
Memilih untuk menutup. Dari wiki kontes-popularitas (di sini ), "Memberi kebebasan kepada peserta untuk memutuskan apa yang harus dilakukan di bagian-bagian penting dan memberi insentif kepada mereka untuk menggunakan kebebasan ini." Saya tidak berpikir membiarkan tantangan terbuka untuk algoritma apa pun dianggap mendorong kreativitas untuk tantangan sederhana, setidaknya tidak sejauh itu berfungsi sebagai popcon. Ini akan lebih cocok sebagai tantangan kode-golf .
mbomb007

Jawaban:

18

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

Diperkecil:

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);}
Ben Voigt
sumber
4
Anda seharusnya menulis kondisi while sebagaia <-- b
justhalf
Dulu ada waktu ketika program C memenangkan kontes popularitas ...
Anubian Noob
Kamu yang terbaik! Bagaimana elegan dan dioptimalkan .. Bisakah Anda melakukan ini dengan bit array?
9

APL (4)

¯A⌽B
  • A adalah jumlah tempat untuk memutar
  • B adalah nama array yang akan diputar

Saya tidak yakin apakah APL benar-benar membutuhkannya, tetapi dalam implementasi saya telah melihat (internal) ini akan membutuhkan waktu yang sebanding A, dan memori konstan.

Jerry Coffin
sumber
+1 jika ini golf :)
Glenn Teitelbaum
Itu tidak melakukannya di tempatnya.
marinus
@marinus: Tentu saja dalam implementasi yang saya lihat.
Jerry Coffin
Bagaimana ini fungsinya? Bisa jadi {⍵⌽⍨-⍺}atau {⌽⍺⌽⌽⍵}. Dalam NARS2000 ini dapat ditulis dengan elegan ⌽⍢⌽.
Adem
5

Ini adalah versi C yang panjang lebar dari ide Colin.

#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);
  }
}
Stephen Montgomery-Smith
sumber
Itu tidak terlihat seperti solusi memori yang konstan, bukan?
microbian
Ya itu adalah solusi memori yang konstan. Barang-barang "malloced" adalah salinan sementara array sehingga saya dapat menyalin data asli ke dalamnya lagi dan lagi, sehingga saya bisa menguji jumlah rotasi yang berbeda.
Stephen Montgomery-Smith
Apa yang diputar sebenarnya adalah fungsi "putar." Ini menggunakan 5 bilangan bulat dan dua ganda. Ia juga memanggil fungsi "gcd" yang menggunakan satu integer, dan menggunakan paling banyak operasi O (log (n)).
Stephen Montgomery-Smith
Oke. Saya menaikkan jawaban Anda.
microbian
@ StephenMontgomery-Smith - bagaimana O(log(n))operasi ini . Lihatlah bymenjadi 1, loop `j 'Anda adalah s_arr / g atau N - ini adalah operasi O (N)
Glenn Teitelbaum
3

C

Tidak yakin apa kriterianya, tetapi karena saya bersenang-senang dengan algoritme, inilah entri saya:

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

Saya akan bermain golf untuk ukuran yang baik juga; 126 byte, dapat dibuat lebih pendek:

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;}}}
treamur
sumber
3

Saya tidak melihat banyak solusi C ++ di sini, jadi saya pikir saya akan mencoba yang satu ini karena tidak menghitung karakter.

Ini adalah rotasi "in-place" yang benar, jadi gunakan 0 ruang ekstra (kecuali pertukaran teknis dan 3 int) dan karena loopnya persis N, juga memenuhi kompleksitas O (N).

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
        }
}
Glenn Teitelbaum
sumber
Catatan: Saya sengaja tidak menggunakan std::rotatekarena itu mengalahkan tujuan
Glenn Teitelbaum
2

Jika Anda melakukan masing-masing kemungkinan siklus rotasi dengan n pada gilirannya (ada GCD (n, len (arr)) dari ini), maka Anda hanya perlu satu salinan sementara elemen array dan beberapa variabel status. Seperti ini, dalam 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
Colin Watson
sumber
1
Saya pikir Anda memiliki ide yang tepat, tetapi cyclevariabel Anda berukuran tidak konstan. Anda harus membuat larik ini saat melangkah.
Keith Randall
2

C (137 karakter)

#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");
}

Fungsi rotatediperkecil menjadi 137 karakter:

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];}
craesh
sumber
2

Factor memiliki tipe bawaan untuk array yang dapat diputar <circular>, jadi ini sebenarnya adalah operasi O (1):

: 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 }

Faktor yang kurang curang setara dengan solusi C mengesankan Ben Voigt:

: 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 }
Björn Lindqvist
sumber
2

JavaScript 45

Tetap pergi golf karena saya suka golf. Nilai maksimumnya adalah O (N) asalkan t<= ukuran array.

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

Untuk menangani tproporsi dalam O (N) berikut ini dapat digunakan (dengan berat 58 karakter):

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

Tidak kembali, edit array di tempat.

George Reith
sumber
1
+1 untukr(o,t) => rot
Conor O'Brien
1

REBEL - 22

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

Input: k dinyatakan sebagai bilangan bulat unary menggunakan _sebagai digit, diikuti oleh spasi, kemudian array bilangan bulat yang dibatasi ruang.

Output: Spasi, lalu array diputar.

Contoh:

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

Kondisi akhir:

 3 4 5 1 2

Penjelasan:

Pada setiap iterasi, ia menggantikan satu _dan array [array] + taildengan tail + [array].

Contoh:

___ 1 2 3 4 5
__ 5 1 2 3 4
_ 4 5 1 2 3
 3 4 5 1 2
Kendall Frey
sumber
Saya tidak berpikir ini O (n). Menyalin sebuah array adalah O(n), dan Anda melakukannya nberkali - kali.
Ben Voigt
1

Jawa

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 di sini .

Javascript Terkecil , 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++}}
ValarDohaeris
sumber
1

Haskell

Ini sebenarnya θ (n), karena pembagiannya adalah θ (k) dan gabungannya adalah θ (nk). Tidak yakin tentang memori.

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
archaephyrryx
sumber
1

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

Memori konstan
O (n) kompleksitas waktu

AMK
sumber
0

Python

def rotate(a, n): a[:n], a[n:] = a[-n:], a[:-n] 
Madison May
sumber
Apakah ini akan menggunakan memori konstan?
SztupY
Hmm ... tidak yakin.
Madison
Ini bukan operasi memori yang konstan.
microbian
Kampret. Panggilan bagus ...
Madison
0

ular sanca

   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
saykou
sumber
Menyalin array bukanlah ruang yang konstan. @ MadisonMay menjawab pada dasarnya melakukan hal yang sama dengan kode ini dengan karakter yang lebih sedikit.
Blckknght
0

vb.net O (n) (bukan memori Konstan)

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
Adam Speight
sumber
0

Rubi

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

C (118)

Mungkin agak terlalu lunak dengan beberapa spesifikasinya. Menggunakan memori yang sebanding shift % length. Juga dapat memutar ke arah yang berlawanan jika nilai pergeseran negatif dilewatkan.

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);}
kardinaliti
sumber
0

Python 2, 57

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

Kalau saja l[-n:len(l)-n]bekerja seperti yang saya harapkan. Itu hanya kembali []karena suatu alasan.

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

Bisakah seseorang memeriksa apakah ini benar-benar memenuhi persyaratan? Saya pikir memang demikian, tetapi saya belum mempelajari CS (belum).

ɐɔıʇǝɥʇu
sumber
0

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);}
mattnewport
sumber
0

Jawa

Tukar elemen k terakhir dengan elemen k pertama, lalu putar elemen lainnya dengan k. Ketika Anda memiliki kurang dari k elemen yang tersisa di akhir, putar dengan k% jumlah elemen yang tersisa. Saya tidak berpikir siapa pun di atas mengambil pendekatan ini. Melakukan persis satu operasi swap untuk setiap elemen, melakukan semuanya di tempat

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)); 
        }
    }
}
Matthew Saltz
sumber
0

Perl 5 , 42 byte

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

Cobalah online!

Subrutin mengambil jarak untuk memutar sebagai parameter pertama dan referensi ke array sebagai parameter kedua. Run time adalah konstan berdasarkan jarak rotasi. Ukuran array tidak mempengaruhi waktu lari. Array dimodifikasi di tempat dengan menghapus elemen dari kanan dan meletakkannya di sebelah kiri.

Xcali
sumber