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}
popularity-contest
array-manipulation
mikrobia
sumber
sumber
Jawaban:
C (104)
Diperkecil:
sumber
a <-- b
APL (4)
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.sumber
{⍵⌽⍨-⍺}
atau{⌽⍺⌽⌽⍵}
. Dalam NARS2000 ini dapat ditulis dengan elegan⌽⍢⌽
.Ini adalah versi C yang panjang lebar dari ide Colin.
sumber
O(log(n))
operasi ini . Lihatlahby
menjadi 1, loop `j 'Anda adalah s_arr / g atau N - ini adalah operasi O (N)C
Tidak yakin apa kriterianya, tetapi karena saya bersenang-senang dengan algoritme, inilah entri saya:
Saya akan bermain golf untuk ukuran yang baik juga; 126 byte, dapat dibuat lebih pendek:
sumber
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).
sumber
std::rotate
karena itu mengalahkan tujuanJika 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:
sumber
cycle
variabel Anda berukuran tidak konstan. Anda harus membuat larik ini saat melangkah.C (137 karakter)
Fungsi
rotate
diperkecil menjadi 137 karakter:sumber
Factor memiliki tipe bawaan untuk array yang dapat diputar
<circular>
, jadi ini sebenarnya adalah operasi O (1):Faktor yang kurang curang setara dengan solusi C mengesankan Ben Voigt:
sumber
JavaScript 45
Tetap pergi golf karena saya suka golf. Nilai maksimumnya adalah O (N) asalkan
t
<= ukuran array.Untuk menangani
t
proporsi dalam O (N) berikut ini dapat digunakan (dengan berat 58 karakter):Tidak kembali, edit array di tempat.
sumber
r(o,t) => rot
REBEL - 22
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:
Kondisi akhir:
Penjelasan:
Pada setiap iterasi, ia menggantikan satu
_
dan array[array] + tail
dengantail + [array]
.Contoh:
sumber
O(n)
, dan Anda melakukannyan
berkali - kali.Jawa
Demo di sini .
Javascript Terkecil , 114 :
sumber
Haskell
Ini sebenarnya θ (n), karena pembagiannya adalah θ (k) dan gabungannya adalah θ (nk). Tidak yakin tentang memori.
sumber
Python 3
Memori konstan
O (n) kompleksitas waktu
sumber
Python
sumber
ular sanca
sumber
vb.net O (n) (bukan memori Konstan)
sumber
Rubi
sumber
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.sumber
Python 2, 57
Kalau saja
l[-n:len(l)-n]
bekerja seperti yang saya harapkan. Itu hanya kembali[]
karena suatu alasan.sumber
Bisakah seseorang memeriksa apakah ini benar-benar memenuhi persyaratan? Saya pikir memang demikian, tetapi saya belum mempelajari CS (belum).
sumber
C ++, 136
sumber
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
sumber
Perl 5 , 42 byte
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.
sumber