Tantangan
Diberikan array integer yang tidak kosong, misalnya:
[5, 2, 7, 6, 4, 1, 3]
Pertama-tama pisahkan ke dalam array di mana tidak ada item yang lebih besar dari sebelumnya (yaitu array yang tidak naik):
[5, 2] [7, 6, 4, 1] [3]
Selanjutnya, balikkan setiap larik:
[2, 5] [1, 4, 6, 7] [3]
Akhirnya, gabungkan semuanya bersama-sama:
[2, 5, 1, 4, 6, 7, 3]
Ini seharusnya yang dihasilkan oleh output / fungsi program Anda. Ulangi prosedur ini cukup kali dan array akan sepenuhnya diurutkan.
Aturan
- Input dan output dapat diberikan melalui metode standar apa pun, dan mungkin dalam format array yang wajar.
- Array input tidak akan pernah kosong, tetapi mungkin mengandung negatif dan / atau duplikat.
- Nilai absolut dari setiap bilangan bulat akan selalu kurang dari 2 31 .
Uji kasus
Semoga ini mencakup semua kasus tepi:
[1] -> [1]
[1, 1] -> [1, 1]
[1, 2] -> [1, 2]
[2, 1] -> [1, 2]
[2, 3, 1] -> [2, 1, 3]
[2, 1, 3] -> [1, 2, 3]
[2, 1, 2] -> [1, 2, 2]
[2, 1, 1] -> [1, 1, 2]
[3, 1, 1, 2] -> [1, 1, 3, 2]
[3, 2, 1, 2] -> [1, 2, 3, 2]
[3, 1, 2, 2] -> [1, 3, 2, 2]
[1, 3, 2, 2] -> [1, 2, 2, 3]
[1, 0, 5, -234] -> [0, 1, -234, 5]
[1, 0, 1, 0, 1] -> [0, 1, 0, 1, 1]
[1, 2, 3, 4, 5] -> [1, 2, 3, 4, 5]
[5, 4, 3, 2, 1] -> [1, 2, 3, 4, 5]
[2, 1, 5, 4, 3] -> [1, 2, 3, 4, 5]
[2, 3, 1, 5, 4] -> [2, 1, 3, 4, 5]
[5, 1, 4, 2, 3] -> [1, 5, 2, 4, 3]
[5, 2, 7, 6, 4, 1, 3] -> [2, 5, 1, 4, 6, 7, 3]
[-5, -2, -7, -6, -4, -1, -3] -> [-5, -7, -2, -6, -4, -3, -1]
[14, 5, 3, 8, 15, 7, 4, 19, 12, 0, 2, 18, 6, 11, 13, 1, 17, 16, 10, 9] -> [3, 5, 14, 8, 4, 7, 15, 0, 12, 19, 2, 6, 18, 11, 1, 13, 9, 10, 16, 17]
Mencetak gol
Ini adalah kode-golf , jadi kode terpendek dalam byte menang.
code-golf
array-manipulation
sorting
Produksi ETH
sumber
sumber
O(n^2)
O(n)
. menukar elemen pertama dan terakhir kemudian menukar elemen terakhir kedua dan kedua dll, ketika Anda sampai di pemberhentian tengah.O(n)
, tetapi membalikkan dapat dibangun langsung ke dalam algoritma (itulah yang dilakukan jawaban JS saya); karena setiap iterasi berulang pada setiap item dalam array sekali, iterasi tunggal adalahO(n)
. (Saya pikir ...)Jawaban:
JavaScript (ES6), 64 byte
Rekursi FTW! Algoritma dasar yang digunakan di sini adalah untuk melacak run non-ascending saat ini dalam array, "mengembalikannya" setiap kali elemen ascending ditemukan. Kami melakukan ini secara rekursif, terus menyatukan hasilnya, sampai kami kehabisan barang. Dengan membuat setiap menjalankan secara terbalik (
[n,...z]
bukan[...z,n]
), kita dapat menghindari yang panjang.reverse()
tanpa biaya.Cuplikan tes
Tampilkan cuplikan kode
sumber
[n,...a]
? Apan
? Apakah itu hanya item pertama dalam array Anda?n
adalah item pertama dalam array, dana
sisanya dari array. Anda dapat menemukan info lebih lanjut di sini ....a
? Apakah itu hanya agar Anda dapat memanfaatkann
? Satu hal lagi, ketika Anda meneleponf(a,q)
, apakahq
diatur ke parameterz
?f=([n])=>...
hanya akan menangkap elemen pertama, danf=([n,a])=>...
hanya akan menangkap yang pertama masukn
dan yang kedua masuka
. Cara lain untuk melakukan apa yangf=([n,...a])=>,,,
akan terjadif=a=>(n=a.unshift(),...
.z
parameter kedua dalam fungsi, ketikaf(a,q)
dipanggil,f
melihatnya sebagaiz
. Semoga ini membantu!Python 3 , 63 byte
Cobalah online!
sumber
Jelly , 8 byte
Cobalah online!
Penjelasan:
sumber
JavaScript (ES6), 70 byte
Tentu, ini sudah dikalahkan oleh jawaban ETHproductions , tapi itu yang terbaik yang bisa saya dapatkan sejauh ini tanpa menggunakan rekursi.
Catatan: Menginisialisasi keduanya
r
dano
ke objek yang sama persisr = o = []
mungkin terlihat seperti ide berbahaya. Tetapi aman untuk melakukannya di sini karenar
segera diberi contoh sendiri (berisi elemen pertamaa
) pada iterasi pertama denganr = [n, ...r]
.Uji kasus
Tampilkan cuplikan kode
sumber
MATL , 15 byte
Input adalah vektor kolom, dengan format
[5; 2; 7; 6; 4; 1; 3]
(titik koma adalah pemisah baris).Cobalah online!
Ambil input
[5; 2; 7; 6; 4; 1; 3]
sebagai contoh.Penjelasan
sumber
Mathematica,
3027 byte3 byte disimpan karena @Martin Ender .
Fungsi anonim. Mengambil daftar angka sebagai input dan mengembalikan daftar angka sebagai output.
sumber
Python 2, 100 byte
Golf yang sangat mengerikan, tetapi saya ingin memposting solusi saya (seseorang tidak hanya mengalahkan Dennis) ...
Uji pada repl.it!
Input harus diberikan sebagai literal daftar Python, seperti
[5, 3, 4, 2, 6, 1]
.Ide dasarnya adalah menggunakan sintaksis slicing Python, memotong setiap bagian yang diperlukan dari array, membalikkannya, dan menambahkannya ke array baru.
sumber
d,L,x=input(),[],0;d+=...
.Pyke,
118 byte ( versi lama )Coba di sini! (bekerja pada versi terbaru)
sumber
Retina , 163 byte
Ya, saya tahu betapa mengerikannya ini. Mendukung nol dan negatif adalah sangat menyenangkan. Hitungan byte mengasumsikan penyandian ISO 8859-1.
Cobalah online
Penjelasan:
sumber
05AB1E ,
19181614 byteDisimpan 2 byte menggunakan trik sortir Luis Mendo
Cobalah online!
Penjelasan
Contoh input
[5, 2, 7, 6, 4, 1, 3]
Solusi 16 byte sebelumnya
sumber
JavaScript (ECMA 6),
121128125119108 byteEkspresi Lambda mengambil satu
Array
parametera
,.Terima kasih kepada @ETHproductions karena membantu saya melihat kesalahan pertama saya.
sumber
return(b+","+c).split`,`
untuk menghemat beberapa byte pada akhirnya.c.unshift
alih-alihc.push
menghapus kebutuhan untuk membalikkanc
. Setelah melakukan ini, saya mendapat 94 byte .Ruby,
6055 byteCukup banyak tantangan yang diminta. Saya mendefinisikan sebuah lambda
s
, yang mengambil arrayx
, dan memotong (mengiris) itu menjadi potongan-potongan kecil di mana elemen berikut akan lebih besar dari. Ini mengembalikan pencacah, yang dapat kita sebut peta dan membalik urutan potongan-potongan, sebelum akhirnya menyatukan semuanya dengan merata, yang menggabungkan elemen-elemen dalam urutan yang ditetapkan ke dalam satu array.Tes
sumber
Brachylog , 10 byte
Cobalah online!
Penjelasan
sumber
c
, ketika dijalankan secara terbalik, perlu mencoba pemisahan menjadi daftar yang lebih sedikit?Dyalog APL ,
715 byteMembutuhkan
⎕ML←3
, yang merupakan standar pada banyak sistem. *∊
minta (ratakan)⌽¨
masing-masing terbalik⍵⊂⍨
argumen dipartisi * dengan memotong di mana setiap elemen yang sesuai lebih besar dari pendahulunya di1+
satu ditambah⍵-
argumen dikurangi⌊/⍵
elemen terkecil dari argumenSolusi 7 byte lama gagal dengan bilangan bulat tidak positif:
Membutuhkan
⎕ML←3
, yang merupakan standar pada banyak sistem. *∊
minta (ratakan)⌽¨
masing-masing terbalik⊂⍨
dipartisi sendiri ** Partition (
⊂
) adalah fungsi yang memotong argumen kanannya di mana argumen kiri yang sesuai lebih besar dari yang sebelumnya. (Sayangnya itu hanya menerima bilangan bulat non-negatif, dan nol memiliki arti khusus.) Dari versi 16, fungsi⊂
ini tersedia pada semua sistem (bahkan yang ada di mana⎕ML≠3
), menggunakan mesin terbang⊆
.sumber
Haskell, 49 byte
Contoh penggunaan:
(%[]) [5,2,7,6,4,1,3]
->[2,5,1,4,6,7,3]
.Pendekatan rekursif. Fungsi
%
mengambil daftar input sebagai parameter pertama dan akumulatorl
yang melacak potongan non-ascending sejauh ini (dalam urutan terbalik). Kasing dasar tercapai ketika daftar input kosong dan hasilnya adalah akumulator. Jika daftar input tidak kosong dan elemen pertamaa
tidak cocok dengan chunk saat ini (any(<a)l
), kembalikan akumulator dan tambahkan panggilan rekursif pada sisa daftar dana
sebagai akumulator baru (l++b%[a]
). Lain, buat panggilan rekursif pada sisa daftar dana
ditambahkan ke akumulator (b%(a:l)
).(%[])
Panggilan fungsi utama%
dengan akumulator kosong.sumber
Retina , 98 byte
Hitungan byte mengasumsikan penyandian ISO 8859-1.
Cobalah online!
sumber
R, 64 byte
Membaca input dari stdin. Kami membagi input menjadi daftar vektor
split()
yang memerlukan variabel faktor yang mengelompokkan input. Faktor dibuat dengan mengambil jumlah kumulatif dari vektor logis yang perbedaannya positif.Pertimbangkan vektor:
Sekarang mengambil perbedaan dan mengawali
F
dengan menjalankany=c(F,diff(x)>0)
akan menghasilkan vektor logis berikut:Mengambil jumlah kumulatif
cumsum(y)
menghasilkan vektor di mana masing-masing kelompok diwakili oleh faktor unik yang dapat kita gabungkan dengansplit
fungsi:sumber
diffinv
daripadacumsum
.Oktaf,
7544 byteBerdasarkan jawaban MATL dari @LuisMendo
Cobalah secara Online!
Jawaban sebelumnya
Cobalah secara Online!
membalikkan array
ambil perbedaan pertama
f
temukan posisi di mana elemen berikutnya kurang dari elemen sebelumnya
Perbedaan pertama dari posisi mengembalikan panjang setiap sub array
gunakan panjang masing-masing sub array
mat2cell
untuk membagi array ke daftar array yang bersarangmembalikkan daftar bersarang
meratakan daftar bersarang
sumber
Pyth - 15 byte
Cobalah online di sini .
sumber
Perl 6 , 59 byte
Solusi berbasis Regex.
Karena ini
SpartaPerl !!m/ /
: Merumuskan array input, dan mencocokkan regex dengan itu.(\-? \d+)
: Cocokkan angka, dan tangkap sebagai$0
.<?{ [>=] $0 }>
: Pernyataan nol-lebar yang hanya cocok jika semua yang$0
ditangkap sejauh ini dalam sub-pertandingan saat ini berada dalam urutan non-naik.([ ] +)+
: Ulangi dua langkah terakhir sesering mungkin, jika tidak, mulailah sub-pertandingan baru.map , [0]
: Iterate atas sub-pertandingan.|+«*.[0].reverse
: Untuk masing-masing, ambil daftar nilai yang cocok dengan$0
, balikkan, paksa nilai ke angka (+«
), dan masukkan ke daftar luar (|
).Perl 6 , 63 byte
Solusi pemrosesan daftar rekursif.
Lebih melelahkan daripada yang saya harapkan.
Meskipun bahasanya memiliki banyak built-in yang nyaman, sepertinya tidak ada satu pun untuk partisi daftar (misalnya seperti Ruby
slice_when
atau HaskelltakeWhile
).sumber
Stacked , noncompeting, 34 byte
Masih terus mengembangkan bahasa ini.
Argumennya terletak pada TOS. Coba di sini!
chunkby
mengambil fungsi dan mengumpulkan array data yang berdekatan yang memenuhi fungsi. Fungsi itu adalah:Ini memberikan array yang sangat menurun.
$revmap
pada dasarnya[rev]map
dan membalikkan setiap item.flat
akhirnya meratakan array.Beberapa kesenangan untuk benar-benar menyortir array:
Output ini (misalnya):
sumber
Python,
151139 BytesDisimpan 12 Bytes berkat @ Flp.Tkc!
Tidak ada di dekat @ Flp.Tkc, apalagi ...
sumber
+= data,
koma trailing yang secara implisit membuat tuple, yang kemudian digabungkan dengan daftar, menambahkan data sebagai elemen terakhir dalam daftar. Dalam konteks ini, lakukanr+=l[i:j+1][::-1],
Python 2, 74 byte
Input masuk
a
, keluaran masukc
sumber
Python 3, 191 Bytes
Saya tidak yakin apakah menggunakan
sorted
fungsi untuk memeriksa diizinkan di sini, tapi saya tidak bisa memikirkan alasan yang bagus untuk menolaknya, dan itu menurunkan jumlah byte saya hingga ~ 30 Bytes.sumber
Clojure, 105 byte
Partisi berpasangan pada angka berurutan, menempatkan
true
atau difalse
antara mereka, partisinot
ketrue
dan angka menjadifalse
danfalse
true
, membalikkan partisi dan mempertahankan nilai numerik.sumber