Temukan jumlah jarak terdekat

10

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.)

Anush
sumber
Bisakah kita menggunakan daftar atau aliran alih-alih array?
Ad Hoc Garf Hunter
@CatWizard Ya Anda bisa!
Anush
1
Bagaimana 1 + 2 + 3berasal dari X = (1,2,3)dan Y = (0,8)?
tamu271314
1
@ guest271314 terdekat nomor dua masing-masing 1, 2dan 3di Yyaitu 0. Dengan demikian perbedaan 1-0, 2-0, 3-0.
dylnan
1
XYjXiYjYj+1Xi+1

Jawaban:

6

Haskell , 70 64 byte

a%b=abs$a-b
x@(a:b)#y@(c:d)|e:_<-d,a%c>a%e=x#d|1>0=a%c+b#y
_#_=0

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

x@(a:b)#(c:d:e)

Pada kasus pertama kita dari sini kita mengikat duntuk e:_dengan e:_<-d. Ini memastikan bahwa ditu tidak kosong dan menetapkan elemen pertama untuk itu e.

YecXax#dYX

Jika kami cocok dengan polanya tetapi tidak melewati syarat yang kami lakukan:

a%c+b#y

XX

0XY

O(|X|+|Y|)

Haskell , 34 byte

O(|X|×|Y|)

x#y=sum[minimum$abs.(z-)<$>y|z<-x]

Cobalah online!

Ad Hoc Garf Hunter
sumber
Saya mengklarifikasi dalam pertanyaan bahwa kita dapat mengasumsikan bahwa menambahkan dua bilangan bulat membutuhkan waktu yang konstan.
Anush
2

Python 2 , 124 120 byte

X,Y=input()
i=j=s=0
while i<len(X):
 v=abs(Y[j]-X[i])
 if j+1<len(Y)and v>=abs(Y[j+1]-X[i]):j+=1
 else:s+=v;i+=1
print s

Cobalah 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 ibertambah atau jbertambah. Dengan demikian loop dieksekusi paling len(X)+len(Y)banyak.

Chas Brown
sumber
Saya mengklarifikasi dalam pertanyaan bahwa kita dapat menganggap menambahkan dua bilangan bulat membutuhkan waktu yang konstan.
Anush
1

C (gcc), 82 byte

n;f(x,y,a,b)int*x,*y;{for(n=0;a;)--b&&*x*2-*y>y[1]?++y:(++b,--a,n+=abs(*x++-*y));}

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 satu aatau bdikurangi pada setiap iterasi dari loop, yang berakhir ketika amencapai 0(dan btidak dapat dikurangi di bawah 0).

Cobalah online!

n;                     // define sum as an integer
f(x,y,a,b)             // function taking two arrays and two lengths
int*x,*y;              // use k&r style definitions to shorten function declaration
{
 for(n=0;              // initialize sum to 0
 a;)                   // keep looping until x (the first array) runs out
                       // we'll decrement a/b every time we increment x/y respectively
 --b&&                 // if y has ≥1 elements left (b>1, but decrements in-place)...
 *x*2-*y>y[1]?         // ... and x - y > [next y] - x, but rearranged for brevity...
 ++y:                  // increment y (we already decremented b earlier);
 (++b,                 // otherwise, undo the in-place decrement of b from before...
 --a,n+=abs(*x++-*y))  // decrement a instead, add |x-y| to n, and then increment x
;}

Beberapa catatan:

  • Alih-alih mengindeks ke dalam array, menambah pointer dan dereferencing secara langsung menghemat byte yang cukup untuk itu layak ( *xvs x[a]dan y[1]vs y[b+1]).

  • The --b&&Kondisi memeriksa b>1secara tidak langsung - jika bini 1, akan mengevaluasi ke nol. Karena ini memodifikasi b, kita tidak perlu mengubahnya di cabang pertama dari terner (yang maju y), tetapi kita perlu mengubahnya kembali di cabang kedua (yang maju x).

  • Tidak returndiperlukan pernyataan, karena ilmu hitam. (Saya pikir itu karena pernyataan terakhir yang akan dievaluasi akan selalu berupa n+=...ekspresi, yang menggunakan register yang sama dengan yang digunakan untuk nilai pengembalian.)

Gagang pintu
sumber
0

Ruby, 88 byte

->(p,q){a=q.each_cons(2).map{|a|a.sum/a.size}
x=a[0]
p.sum{|n|x=a.pop if n>x
(n-x).abs}}

Cobalah online!

Selain itu, untuk bersenang-senang, fungsi anonim yang lebih pendek yang tidak cukup memenuhi batasan kompleksitas:

->(a,b){a.map{|x|x-b.min_by{|y|(x-y).abs}}.sum}
Tango
sumber
Bisakah Anda jelaskan secara sederhana bagaimana kode ini bekerja? Saya tidak tahu apakah itu berjalan dalam waktu linier.
Anush
2
Ini gagal pada test case pertama dalam pertanyaan, serta input seperti [5, 6], [0, 1, 5].
Gagang Pintu
0

JavaScript (Node.js) , 80 byte

x=>g=(y,i=0,j=0,v=x[i],d=v-y[j],t=d>y[j+1]-v)=>1/v?g(y,i+!t,j+t)+!t*(d>0?d:-d):0
  • Itu berjalan di O (| X | + | Y |): Setiap rekursi dijalankan di O (1), dan itu rekursif | X | + | Y | waktu.
    • x, ydilewatkan dengan referensi, yang tidak menyalin konten
  • 1/vpalsu jika x[i]berada di luar jangkauan, benar sebaliknya
  • t-> d>y[j+1]-v-> v+v>y[j]+y[j+1]salah selama ketentuan berikut memenuhi. Dan yang artinya y[j]adalah angka yang paling dekat dengan vdiy
    • vkurang dari (y[j]+y[j+1])/2, atau
    • y[j+1]berada di luar jangkauan, yang akan dikonversi menjadi NaN, dan dibandingkan dengan NaNhasilfalse
      • itu sebabnya kita tidak bisa membalikkan >tanda untuk menghemat 1 byte lagi
  • tselalu merupakan nilai boolean, dan *mengubahnya menjadi 0/ 1sebelum menghitung

Cobalah online!

tsh
sumber
0

Mathematica, 40 byte

x = {1, 5, 9};
y = {3, 4, 7};

Norm[Flatten[Nearest[y] /@ x] - x]

Jika Anda harus membuat program lengkap, dengan input:

f[x_,y_]:= Norm[Flatten[Nearest[y] /@ x] - x]

Inilah waktu untuk 1.000.000 poin (sampel setiap 10.000) untuk y:

masukkan deskripsi gambar di sini

Dekat dengan linier.

David G. Stork
sumber
1
Jawaban ini adalah potongan kode karena input Anda diambil sebagai variabel yang sudah ada sebelumnya. Anda harus memformatnya menjadi sub-rutin atau program lengkap.
Ad Hoc Garf Hunter
Saya juga agak curiga bahwa ini bekerja dalam waktu linier, apakah Anda punya alasan mengapa harus? Mathematica cenderung agak buram dalam kerumitan bawaannya.
Ad Hoc Garf Hunter