Temukan nomor terdekat terdekat

30

Tugas

Diberikan berbagai bilangan bulat, misalnya:

[-1,476,578,27,0,1,-1,1,2]

dan indeks dari array itu (contoh ini menggunakan pengindeksan berbasis 0 , meskipun Anda dapat menggunakan pengindeksan berdasarkan 1 juga.):

         index = 5
                 v
[-1,476,578,27,0,1,-1,1,2]

Kemudian kembalikan angka terdekat yang lebih besar dari elemen pada indeks itu . Dalam contoh, angka terdekat yang lebih besar dari 1 adalah 27 (pada 2 indeks jauhnya).

         index = 5
                 v
[-1,476,578,27,0,1,-1,1,2]
            ^
Nearest greater number

Output = 27

Asumsi

  • Terdekat tidak termasuk pembungkus.
  • Program tidak akan pernah diberi array dengan panjang 1 (misalnya; [55]).
  • Anda harus menganggap selalu ada angka lebih besar dari elemen yang diberikan.
  • Jika ada 2 angka lebih besar dari elemen pada jarak yang sama, Anda dapat kembali salah satunya .

Pasangan I / O

Input:
Index = 45
Array = [69, 43, 89, 93, 62, 25, 4, 11, 115, 87, 174, 60, 84, 58, 28, 67, 71, 157, 47, 8, 33, 192, 187, 87, 175, 32, 135, 25, 137, 92, 183, 151, 147, 7, 133, 7, 41, 12, 96, 147, 9, 134, 197, 3, 107, 164, 90, 199, 21, 71, 77, 62, 190, 122, 33, 127, 185, 58, 92, 106, 26, 24, 56, 79, 71, 24, 24, 114, 17, 84, 121, 188, 6, 177, 114, 159, 159, 102, 50, 136, 47, 32, 1, 199, 74, 141, 125, 23, 118, 9, 12, 100, 94, 166, 12, 9, 179, 147, 149, 178, 90, 71, 141, 49, 74, 100, 199, 160, 120, 14, 195, 112, 176, 164, 68, 88, 108, 72, 124, 173, 155, 146, 193, 30, 2, 186, 102, 45, 147, 99, 178, 84, 83, 93, 153, 11, 171, 186, 157, 32, 90, 57, 181, 5, 157, 106, 20, 5, 194, 130, 100, 97, 3, 87, 116, 57, 125, 157, 190, 83, 148, 90, 44, 156, 167, 131, 100, 58, 139, 183, 53, 91, 151, 65, 121, 61, 40, 80, 40, 68, 73, 20, 135, 197, 124, 190, 108, 66, 21, 27, 147, 118, 192, 29, 193, 27, 155, 93, 33, 129]
Output = 199

Input:
Index = 2
Array = [4,-2,1,-3,5]
Output = 4 OR 5

Input:
Index = 0
Array = [2124, -173, -155, 146, 193, -30, 2, 186, 102, 4545]
Output = 4545

Input:
Index = 0
Array = [1,0,2,3]
Output = 2

Input:
Index = 2
Array = [3,-1,-3,-2,5]
Output = -1 OR -2
Graviton
sumber
Bisakah Anda menambahkan test case di mana ia mencari hasil ke kiri, bukan ke kanan? yaitu1; [7,1,-4,2]
Kevin Cruijssen
Saya pikir 2; [3,-1,-3,-2,5]ini adalah test case yang bagus. Ada angka positif, tetapi hasilnya negatif.
Stewie Griffin
Bisakah saya menggunakan 2-diindeks?
Titus
@Itus maksud saya jika Anda benar-benar ingin
Graviton

Jawaban:

7

MATL , 10 byte

yt&y)>fYk)

Ini menggunakan pengindeksan berbasis 1. Cobalah online!

Penjelasan

Pertimbangkan input [4,-2,1,-3,5], 3sebagai contoh.

y     % Take two inputs implicitly. Duplicate 2nd-top element in the stack
      % STACK: [4,-2,1,-3,5], 3, [4,-2,1,-3,5]
t     % Duplicate top of the stack
      % STACK: [4,-2,1,-3,5], 3, [4,-2,1,-3,5], [4,-2,1,-3,5]
&y    % Duplicate 3rd-top element in the stack
      % STACK: [4,-2,1,-3,5], 3, [4,-2,1,-3,5], [4,-2,1,-3,5], 3
)     % Index: select elements from first input as indicated by second input
      % STACK: [4,-2,1,-3,5], 3, [4,-2,1,-3,5], 1
>     % Greater than, element-wise
      % STACK: [4,-2,1,-3,5], 3, [1,0,0,0,1]
f     % Find: gives indices of non-zero entries
      % STACK: [4,-2,1,-3,5], 3, [1,5]
Yk    % Closest element: gives closest element of each entry in second input
      % ([1,5]) to each entry in the first input (3). In case of a tie it 
      % gives the left-most one
      % STACK: [4,-2,1,-3,5], 1
)     % Index: select elements from first input as indicated by second input
      % STACK: 4
      % Implicitly display
Luis Mendo
sumber
2
Apakah Anda punya penjelasan?
Nick Clifford
@NickClifford Tentu! Saya sedang menunggu klarifikasi OP. Penjelasan ditambahkan
Luis Mendo
6

Jelly , 10 byte

ị<ṛTạ⁸$ÞḢị

Cobalah online!

Dennis
sumber
Saya mengutak-atik selama bertahun-tahun mencoba menyortir untuk bekerja dengan nilai absolut :(
Jonathan Allan
5

Jelly , 11 12 byte

+1 byte - Pembungkus tidak diizinkan.

Jạż⁸ṢZṪ»\Q2ị

1-diindeks.

Cobalah online!


Byter 11 sebelumnya (pembungkus indeks), 0-diindeks:

ṙżU$Fµ>ḢTḢị
Jonathan Allan
sumber
Ini gagal pada mis 0 [1,0,2,3].
Ørjan Johansen
@ ØrjanJohansen Ah - ia kembali 3, yaitu 1 jauhnya jadi, um, ya "terdekat" tidak didefinisikan ...
Jonathan Allan
1
Saya meminta OP untuk menambahkan test case itu.
Ørjan Johansen
4

JavaScript (ES6), 57 55 byte

Mengambil array adan indeks idalam sintaks currying (a)(i).

a=>g=(i,p)=>(x=a[i-p])>a[i]||(x=a[i+p])>a[i]?x:g(i,-~p)

Uji kasus

Arnauld
sumber
Bisakah Anda tidak menggunakan |bukan ||?
Neil
@Neil Tidak, kami tidak ingin xditimpa ketika kondisi pertama terpenuhi.
Arnauld
3

PHP, 106 Bytes

<?for($y=($a=$_GET[0])[$x=$_GET[1]];$y>=$a[$x-++$i]&&$y>=$a[$x+$i];);echo$y<$a[$x+$i]?$a[$x+$i]:$a[$x-$i];

Versi Online

Jörg Hülsermann
sumber
Sepertinya ini tidak berfungsi untuk test case pertama.
Nick Clifford
@NickClifford Sekarang seharusnya berfungsi. Saya telah mengambil pendekatan yang salah
Jörg Hülsermann
3

Haskell , 48 byte

i%l=minimum[[j*j,x]|(j,x)<-zip[-i..]l,x>l!!i]!!1

Cobalah online! Kerangka uji dari Ørjan Johansen.

Tidak
sumber
Anda dapat menyimpan byte dengan menggunakan daftar dan !!1sebagai gantinya (cukup ubah Integerke Intdalam header).
Ørjan Johansen
@ ØrjanJohansen Terima kasih, saya telah mencobanya dan tidak yakin mengapa ia mengeluh tentang tipe.
xnor
2

x86-64 Majelis, 40 byte

Terinspirasi oleh menganalisis solusi Johan du Toit dan C 2501 , berikut ini adalah fungsi yang dapat dirakit dengan MASM untuk platform x86-64.

Ini mengikuti konvensi pemanggilan Microsoft x64 untuk parameter yang lewat, sehingga total panjang array dilewatkan ECX, posisi yang diinginkan dilewatkan EDX, dan pointer ke array integer dilewatkan dalamR8 (ini adalah platform 64-bit, jadi itu adalah pointer 64-bit).

Ini mengembalikan hasil ("angka terbesar terdekat") di EAX.

             FindNearestGreater PROC      
8B F2       \    mov     esi, edx     ; move pos parameter to preferred register
8B D9       |    mov     ebx, ecx     ; make copy of count (ecx == i; ebx == count)
            | MainLoop:
8B C6       |    mov     eax, esi     ; temp  = pos
2B C1       |    sub     eax, ecx     ; temp -= i
99          |    cdq
33 C2       |    xor     eax, edx
2B C2       |    sub     eax, edx     ; temp = AbsValue(temp)
            | 
41 8B 14 B0 |    mov     edx, DWORD PTR [r8+rsi*4]
41 39 14 88 |    cmp     DWORD PTR [r8+rcx*4], edx
7E 04       |    jle     KeepGoing    ; jump if (pValues[i] <= pValues[pos])
3B D8       |    cmp     ebx, eax
77 02       |    ja      Next         ; jump if (count > temp)
            | KeepGoing:
8B C3       |     mov     eax, ebx    ; temp = count
            | Next:
8B D8       |     mov     ebx, eax    ; count = temp
E2 E3       |     loop    MainLoop    ; equivalent to dec ecx + jnz, but smaller (and slower)
            | 
            |     ; Return pValues[temp + pos]
03 C6       |     add     eax, esi
41 8B 04 80 |     mov     eax, DWORD PTR [r8+rax*4]
C3          /     ret
             FindNearestGreater ENDP

Jika Anda ingin menyebutnya dari kode C, prototipe akan menjadi:

extern int FindNearestGreater(unsigned int count,
                              unsigned int pos,
                              const    int *pValues);
Cody Grey
sumber
1

Ruby , 64 byte

->a,i{a[(0...a.size).select{|j|a[j]>a[i]}.min_by{|j|(i-j).abs}]}

Cobalah online!

Nilai Tinta
sumber
1

Ohm , 20 byte

Pada dasarnya terjemahan jawaban Ruby ini .

Dl#)░┼_ª┼┘ª>;╥┘_-A;ª

Cobalah online!

Penjelasan akan datang nanti saat saya tidak mengerjakan pekerjaan rumah.

Nick Clifford
sumber
1

Haskell , 53 byte

(#)mengambil Intdan daftar Ints atau Integers (sebenarnya Ordjenis apa pun ), dan mengembalikan elemen daftar.

n#l=[x|i<-[1..],x:_<-(`drop`l)<$>[n-i,n+i],x>l!!n]!!0

Bagaimana itu bekerja

  • nadalah indeks yang diberikan dan ldaftar / "array" yang diberikan.
  • i, mengambil nilai dari 1 ke atas, adalah jarak dari yang nsaat ini sedang diuji.
  • Untuk masing-masing i, kami memeriksa indeks n-idan n+i.
  • xadalah elemen lyang diuji. Jika lulus tes itu akan menjadi elemen dari pemahaman daftar yang dihasilkan.
    • Pengindeksan indeks sewenang-wenang dengan !!bisa memberikan kesalahan di luar batas, sementara dropsebaliknya mengembalikan seluruh daftar atau daftar kosong dalam kasus itu. Pola cocok dengan x:_memeriksa bahwa hasilnya tidak kosong.
    • x>l!!nmenguji bahwa elemen kita lebih besar dari elemen pada indeks n(yang dijamin ada).
    • !!0 pada akhirnya mengembalikan kecocokan / elemen pertama dari pemahaman daftar.

Cobalah online!

Ørjan Johansen
sumber
1

Brachylog , 17 byte

hH&∋₎<.&t:I≜+:H∋₍

Cobalah online!

Penjelasan

hH                      Call the list H
  &∋₎<.                 Output is greater than the number at the specified index
       &t:I≜            Label I (0, then 1, then -1, then 2, then -2, …)
            +           Sum I with the input Index
             :H∋₍       Output is the element of H at index <the sum>
Fatalisasi
sumber
1

Java (OpenJDK 8) , 98 byte

int f(int n,int[]a){for(int s=1,i=1,x=a[n];;n+=i++*s,s=-s)if(0<=n&n<a.length&&a[n]>x)return a[n];}

Cobalah online!

Periksa indeks dalam urutan yang ditentukan oleh jumlah sebagian dari jumlah berikut:

initial value + 1 - 2 + 3 - 4 + 5 - 6 + ...
Biarawati Bocor
sumber
Saya baru saja membaca pertanyaan dan ingin mulai menulis jawaban .. Btw, mengapa s=1,dan ,s=-s, tidak ada gunanya dalam jawaban Anda .. Apakah Anda lupa menghapusnya dari pendekatan lama?
Kevin Cruijssen
1
@KevinCruijssen itu kesalahan dan saya memperbaikinya sekarang. Itu melewati testcases karena di semua testcases itu, angka terdekat yang paling besar adalah di sebelah kanan.
Leaky Nun
1

C, 69 byte

t;b;f(*d,c,p){for(b=c;c--;)d[c]>d[p]&(t=abs(p-c))<b?b=t:0;*d=d[p+b];}

Argumen pertama adalah argumen masuk / keluar. Output disimpan dalam elemen pertamanya.

Lihat itu berfungsi online .

2501
sumber
1

R, 59 byte

function(l,i)l[j<-l>l[i]][which.min(abs(1:length(l)-i)[j])]

mengembalikan fungsi anonim. Jika ada dua elemen yang lebih besar pada jarak yang sama, akan mengembalikan yang pertama (indeks lebih rendah).

Cobalah online!

Giuseppe
sumber
1

Pyth - 28 byte

JEehf>@T1@JQo@NZm(adQ@Jd)UlJ

Cobalah

Maria
sumber
1

PHP, 73 byte

function($i,$a){for(;$b<=$a[$i];)$b=max($a[++$d+$i],$a[$i-$d]);return$b;}

closure mengambil indeks dan array berbasis 0 dari argumen. Verifikasi semua kasus uji .

Titus
sumber
Bukan nilai lebih tinggi berikutnya. Anda memerlukan nilai dengan jarak terendah yang lebih tinggi
Jörg Hülsermann
@ JörgHülsermann Terima kasih telah menunjukkan.
Titus
0

Pyth, 16 byte

JEh>#@JQ@LJaDQUJ

Suite uji .

Biarawati Bocor
sumber
0

C, 110 byte

c,o;e(g,l,f)int*g;{for(o=g[l],c=1;c<f;c++)l+c<f&&g[l+c]>o?o=g[l+c],c=f:0,l-c>=0&&g[l-c]>o?o=g[l-c],c=f:0;g=o;}

Cobalah online

Johan du Toit
sumber
0

Java, 96 Bytes

int f(int n,int[]a){for(int s=1,i=1,x=a[n];0>(n+=i++*s)|n>=a.length||a[n]<=x;s=-s);return a[n];}

Identifier diberi nama seperti jawaban @Leaky Nun. Selain itu, sebagian besar bagian telah disejajarkan pada dasarnya sama: Sebagai perbandingan, iftelah digantikan oleh for-condition (mengorbankan titik koma tambahan). Sebuah titik dua telah dihapus dengan memindahkan bagian-tambahan ke kondisi (sehingga tanda kurung dari pernyataan-sebelumnya sebelumnya secara praktis "dipindahkan") - mengubah & menjadi | tidak berdampak pada jumlah karakter.

Johannes
sumber
0

Clojure, 95 byte

#(%(nth(nth(sort-by first(for[i(range(count %)):when(>(% i)(% %2))][(Math/abs(- i %2))i]))0)1))

Ini adalah yang terpendek yang bisa saya buat :( Saya juga mencoba bermain-main dengan ini tetapi tidak bisa membawanya ke garis finish:

#(map(fn[f c](f c))[reverse rest](split-at %2 %))
NikoNyrh
sumber