Gabungkan Sortir
Dalam tantangan ini, Anda akan menerapkan subrutin gabungan dari semacam gabungan. Khususnya, Anda harus membuat fungsi atau program atau kata kerja atau serupa yang mengambil dua daftar, masing-masing diurutkan dalam urutan meningkat, dan menggabungkannya ke dalam satu daftar diurutkan dalam urutan meningkat. Persyaratan:
- Algoritme Anda harus mengambil jumlah waktu linear asimtotik dalam ukuran input. Tolong berhenti memberikan solusi O (n ^ 2).
- Anda tidak boleh menggunakan fungsi bawaan yang mampu mengurutkan daftar, atau menggabungkan daftar, atau hal-hal seperti itu. Kebijaksanaan penulis.
- Kode harus dapat menangani elemen berulang.
- Jangan khawatir tentang daftar kosong.
Contoh:
merge([1],[0,2,3,4])
[0,1,2,3,4]
merge([1,5,10,17,19],[2,5,9,11,13,20])
[1, 2, 5, 5, 9, 10, 11, 13, 17, 19, 20]
Ini kode-golf , jadi semoga kode terpendek menang!
b=a;b=b.length
dapat menduplikasi seluruh arraya
(dan menghasilkan waktu O (n ^ 2) jika dieksekusi untuk setiap elemen) atau menduplikat hanya referensi ke array (O (n) waktu). Yang mana yang diperhitungkan?Jawaban:
Rebmu (
3532 karakter)Uji
Tentang
Rebmu adalah dialek Rebol yang memungkinkan 'meremas' kode reguler untuk situasi yang membutuhkan keringkasan. Tanpa basa-basi, kode ini bekerja seperti:
Saya percaya ini memenuhi persyaratan O (n) karena blok sampai paling banyak dilingkarkan sebanyak panjang input (dan
reverse
hanya mengganti urutan wadah blok input, bukan blok itu sendiri). Menggunakantake
mungkin adalah kebebasan, tetapi masih merupakan efisiensi kecil.Rebol (
8375 karakter)Hanya sedikit berbeda: di Rebol, path adalah ekspresi yang lebih pendek dari
first
atausecond
.a
adalah blok input yang berisi dua blok:sumber
Solusi OP:
Haskell
494440Python
1311051019993Dengan terima kasih kepada @Evpok:
sumber
a%b=a++b
setelah pencocokan pola utama untuk menangani daftar kosong, yang akan memangkas beberapa karakter.Python (79)
Python (95, jika kita tidak diizinkan untuk mengembalikan generator)
Itertools adalah solusi untuk semua masalah duniawi.
Bonus: keduanya bekerja berdasarkan jumlah daftar yang berubah-ubah, dan LAKUKAN khawatir tentang daftar kosong (seperti, mereka akan dengan senang hati mengambil 2 daftar kosong, dan mengembalikan daftar kosong, atau mengambil 1 daftar kosong dan 1 daftar tidak kosong, dan mereka akan mengembalikan yang tidak kosong. Fitur tambahan lain dari 2 yang tidak menghasilkan: mereka juga akan berjalan tanpa argumen, dan hanya mengembalikan daftar kosong.)
Tidak Disatukan:
sumber
r+=[...]
sebagai gantinyar.append(...)
(hemat 4 karakter setiap kali)C - 75
Ini beroperasi pada
NULL
array yang diakhiriint *
, meskipun itu akan bekerja sama baiknya untuk pointer ke tipe lain dengan mengganti fungsi perbandingan yang sesuai untuk**b < **a
(misalnya,strcmp(*b, *a) < 0
).Tidak Disatukan:
sumber
Golfscript,
2927302926 byteatau
Bagaimana itu bekerja
Perintah
akan diproses sebagai berikut:
Outputnya adalah:
sumber
[1 1 1 ... 2]
dan[1 1 1 ... 3]
), karena membandingkan array (daripada elemen pertama mereka) akan sangat lambat dalam kasus ini.J -
4233Versi modifikasi dari sini + komentar dari @algorithmshark
k
menambahkan kepala array kanan ke ekor gabungan dari kedua array.k~
sama, tetapi dengan array terbalik.(>&{.)
membandingkan kepala. Kode akan memunculkan kesalahan jika salah satu array kosong, dalam hal ini kami mengembalikan hanya gabungan mereka,
.sumber
/:~ a,b
adalah jawaban terlarang (bersama[:/:~,
), bahwa Anda memotret untuk jawaban terpendek yang tidak termasuk/:
, kan?m=:k~`k@.(>&{.)`,@.(0=*&#)
menghemat 2 char.k=:(m}.),~0{]
andm=:k~`k@.(>&{.) ::,
. Kami menggunakan0{
untuk melempar kesalahan ketika daftar kosong, dan kemudian menangkap kesalahan itu dan keluar bersama,
.JavaScript (ES6),
6979 byteBagaimana itu bekerja
sumber
<
operator tidak valid karena melakukan perbandingan string:f([123, 456, 789], [1, 2, 3, 4, 5]) => [1, 123, 2, 3, 4, 456, 5, 789]
[]
dan kemudian mengubahnya menjadi string membutuhkan O (n) waktu. Melakukannya sekali untuk semua elemen n dari array membutuhkan O (n ^ 2) waktu.Python
(63) (69)(71)Saya menulis ini sebelum melihat komentar OP pada runtimes dari jawaban lain, jadi ini adalah solusi lain yang O (n) dalam algoritma tetapi tidak implementasi.
sumber
return[a.pop(0)]+(a and m(a,b)or b)
Haskell, 35 byte
Haskell, 30 byte (tidak bersaing)
Versi yang tidak bersaing ini hanya menjamin runtime linier jika
a
danb
memiliki elemen yang terpisah; selain itu masih berjalan dengan benar tetapi dapat menggunakan waktu kuadratik.sumber
PHP
91 9891 bytesunting # 1: Kosong
$b
membutuhkan kondisi tambahan di kurung kurawal (+7).sunting # 2: pegolf minor
sunting # 3: menambahkan versi kedua
cukup lurus ke depan. Bagian terbaik adalah ternary di dalam
array_shift
(yang gagal jika Anda mencobanya tanpa keriting)
atau
ungolfed
uji
sumber
$a&(!$b|$a[0]<$b[0])?$a:$b
bukan${$a&(!$b|$a[0]<$b[0])?a:b}
array_shift
Parameter digunakan oleh referensi. Itu harus menjadi variabel; sebuah ekspresi tidak akan berhasil.Ayo, 124 karakter
sumber
JavaScript - 133
Jenis pendekatan yang sama dengan OP.
sumber
perl, 87 karakter / perl 5.14, 78 + 1 = 79 karakter
Implementasi ini mengganggu referensi array input. Selain itu, itu sangat mudah: sementara kedua array memiliki sesuatu, bergeser ke bawah dari keduanya. Kemudian kembalikan bit yang digabungkan bergabung dengan bit yang tersisa (hanya satu dari @ $ x atau @ $ y akan tetap). Perl5 langsung, 87 karakter:
Menggunakan perl 5.14.0 dan pergeseran arrayref yang baru: 78 karakter + 1 penalti char = 79 karakter:
sumber
*
bukannya&&
akan menghemat satu byte. Dan bahkan lebih jikasub M{map{shift(!@$x+@$y*($$y[0]<$$x[0])?$y:$x)}map@$_,($x,$y)=@_}
Jawa: 144
Ini sangat mudah. Fungsi yang mengambil dua array dan mengembalikan satu, versi gabungan, golf dan tanpa pembungkus kompilasi:
Tidak disatukan (dengan pembungkus yang dapat dikompilasi dan dapat dijalankan):
Contoh eksekusi:
Setiap tips untuk dipersingkat akan dihargai.
sumber
Scala, 97 byte
Solusi rekursif dengan O (n). Untuk mempersingkat kode, terkadang operasi dilakukan dengan mengganti 2 parameter yang dapat dipertukarkan, yaitu f (a, b) panggilan f (b, a).
Tidak Disatukan:
sumber
APL (32)
Penjelasan:
sumber
LISP, 117 byte
Algoritma berakhir dengan
n + 1
iterasi, di manan
adalah panjang daftar input terpendek.sumber
PYG (50)
PYG (64, sekali lagi, jika tidak ada generator yang diizinkan.):
Adaptasi jawaban Python saya .
sumber
Python - 69 byte
Jika urutan input dan output menurun, ini bisa disingkat menjadi 61 byte :
Dan lebih jauh ke 45 byte jika generator diizinkan:
sumber
pop(0)
dapat diimplementasikan dalam O (1) dan+=
setidaknya dapat diimplementasikan lebih baik daripada O (n) (lihat tautan). Omong-omong, solusi Anda menggunakan+=
(yaitu,append
danextend
) sesering milik saya. Lagi pula, semua itu adalah pertanyaan implementasi (sejauh yang saya tahu), jadi dalam implementasi Python (fiktif), di mana daftar diimplementasikan sebagai daftar, fungsi saya adalah O (n). Akhirnya pertanyaan Anda membutuhkan algoritme menjadi O (n), dan pertanyaan saya adalah.Perl 6: 53 karakter
Bergeser dari mana saja dari
a
ataub
memiliki nilai lebih kecil, hinggaa
XORb
(a^b
) benar. Lalu kembalikan apa pun yang tersisa, ratakan ([]
) array ke dalam daftar (a[],b[]
).Dengan asumsi pergeseran dari awal array adalah O (n), kasus terburuk adalah dua perbandingan dan satu shift per elemen, sehingga algoritmenya adalah O (n).
sumber
JavaScript (ES5)
908690 bytesunting: (90 -> 86) Memindahkan terner ke dalam untuk kondisi loop. Ide yang dicuri dari Dennis.
sunting: (86 -> 90) Array yang dihapus ke String cast, karena melanggar persyaratan O (n) .
sumber
Mathematica,
137135Memasukkan:
Keluaran:
Tidak Disatukan:
Mungkin bisa berbuat lebih baik.
sumber
m[a:{x___,y_},b:{___,z_}]:=If[y<z,b~m~a,{x}~m~b~Join~{y}];{}~m~b_=b;
R, 80
Solusi yang sama seperti di Scala dan bahasa lainnya. Saya tidak begitu yakin tentang x [-1] adalah O (1).
sumber
Mathematica, 104 byte
Fungsi anonim, menyimpan panjang dua daftar input dalam variabel
m
dann
, kemudian setiap iterasi dariDo
loopSow
merupakan elemen dari satu daftar yang menambah penghitung untuk daftar itu (i
untuk yang pertama,k
untuk yang kedua) dengan satu. Jika salah satu penghitung melebihi panjang daftar,If
pernyataan akan selaluSow
elemen dari daftar lainnya. Setelahn+m
operasi, semua elemen telah diurus.Reap
atau lebih tepatnya bagian[[2,1]]
dari outputnya adalah daftar elemen-elemen sesuai urutannyaSow
n.Saya tidak yakin dengan internal (mengakses bagian daftar
O(1)
operasi atau tidak), tetapi pengaturan waktu tampak cukup linier pada mesin saya sehubungan dengan panjang daftar input.sumber