Untuk tugas ini, kode Anda harus mengambil dua array diurutkan dari integer X dan Y sebagai input. Ini harus menghitung jumlah jarak absolut antara setiap bilangan bulat di X dan nomor terdekatnya di Y.
Contoh:
X = (1 5,9)
Y = (3,4,7)
Jaraknya 2 + 1 + 2.
X = (1,2,3)
Y = (0,8)
Jaraknya 1 + 2 + 3.
Kode Anda dapat mengambil input dengan cara apa pun yang nyaman.
Pembatasan utama adalah bahwa kode Anda harus berjalan dalam waktu linier dalam jumlah dari panjang dua array. . (Anda dapat mengasumsikan bahwa menambahkan dua bilangan bulat membutuhkan waktu yang konstan.)
1 + 2 + 3
berasal dariX = (1,2,3)
danY = (0,8)
?1
,2
dan3
diY
yaitu0
. Dengan demikian perbedaan1-0
,2-0
,3-0
.Jawaban:
Haskell ,
7064 byteCobalah online!
Penjelasan
Pertama kita mendefinisikan
(%)
perbedaan mutlak antara dua angka. Kemudian kita definisikan(#)
sebagai fungsi yang menarik. Di baris pertama kami cocok ketika kedua daftar tidak kosong:Pada kasus pertama kita dari sini kita mengikat
d
untuke:_
dengane:_<-d
. Ini memastikan bahwad
itu tidak kosong dan menetapkan elemen pertama untuk itue
.e
c
a
x#d
Jika kami cocok dengan polanya tetapi tidak melewati syarat yang kami lakukan:
Haskell , 34 byte
Cobalah online!
sumber
Python 2 ,
124120 byteCobalah online!
Disimpan 4 byte dengan berpindah ke program versus fungsi.
Memenuhi batasan kompleksitas waktu dimungkinkan karena kedua daftar diurutkan. Perhatikan bahwa setiap kali di sekitar loop, baik
i
bertambah atauj
bertambah. Dengan demikian loop dieksekusi palinglen(X)+len(Y)
banyak.sumber
C (gcc), 82 byte
Ini membutuhkan input sebagai dua array integer dan panjangnya (karena C tidak memiliki cara untuk mendapatkan panjangnya). Ini dapat ditunjukkan untuk dijalankan
O(a+b)
karena salah satua
ataub
dikurangi pada setiap iterasi dari loop, yang berakhir ketikaa
mencapai0
(danb
tidak dapat dikurangi di bawah0
).Cobalah online!
Beberapa catatan:
Alih-alih mengindeks ke dalam array, menambah pointer dan dereferencing secara langsung menghemat byte yang cukup untuk itu layak (
*x
vsx[a]
dany[1]
vsy[b+1]
).The
--b&&
Kondisi memeriksab>1
secara tidak langsung - jikab
ini1
, akan mengevaluasi ke nol. Karena ini memodifikasib
, kita tidak perlu mengubahnya di cabang pertama dari terner (yang majuy
), tetapi kita perlu mengubahnya kembali di cabang kedua (yang majux
).Tidak
return
diperlukan pernyataan, karena ilmu hitam. (Saya pikir itu karena pernyataan terakhir yang akan dievaluasi akan selalu berupan+=...
ekspresi, yang menggunakan register yang sama dengan yang digunakan untuk nilai pengembalian.)sumber
Ruby, 88 byte
Cobalah online!
Selain itu, untuk bersenang-senang, fungsi anonim yang lebih pendek yang tidak cukup memenuhi batasan kompleksitas:
sumber
[5, 6], [0, 1, 5]
.JavaScript (Node.js) , 80 byte
x
,y
dilewatkan dengan referensi, yang tidak menyalin konten1/v
palsu jikax[i]
berada di luar jangkauan, benar sebaliknyat
->d>y[j+1]-v
->v+v>y[j]+y[j+1]
salah selama ketentuan berikut memenuhi. Dan yang artinyay[j]
adalah angka yang paling dekat denganv
diy
v
kurang dari(y[j]+y[j+1])/2
, atauy[j+1]
berada di luar jangkauan, yang akan dikonversi menjadiNaN
, dan dibandingkan denganNaN
hasilfalse
>
tanda untuk menghemat 1 byte lagit
selalu merupakan nilai boolean, dan*
mengubahnya menjadi0
/1
sebelum menghitungCobalah online!
sumber
Mathematica, 40 byte
Jika Anda harus membuat program lengkap, dengan input:
Inilah waktu untuk 1.000.000 poin (sampel setiap 10.000) untuk
y
:Dekat dengan linier.
sumber