Dengan array a yang hanya berisi angka dalam rentang dari 1 hingga a.length, cari nomor duplikat pertama yang kemunculannya yang kedua memiliki indeks minimal. Dengan kata lain, jika ada lebih dari 1 angka duplikat, kembalikan angka yang kemunculannya yang kedua memiliki indeks yang lebih kecil daripada kemunculan kedua dari angka lainnya. Jika tidak ada elemen seperti itu, program / fungsi Anda dapat mengakibatkan perilaku yang tidak terdefinisi.
Contoh:
Sebab a = [2, 3, 3, 1, 5, 2]
, output harus
firstDuplicate(a) = 3
.
Ada 2 duplikat: angka 2 dan 3. Kemunculan kedua 3 memiliki indeks lebih kecil daripada kemunculan kedua 2, jadi jawabannya adalah 3.
Sebab a = [2, 4, 3, 5, 1]
, output harus
firstDuplicate(a) = -1
.
Ini adalah kode-golf , jadi jawaban tersingkat dalam byte menang.
BONUS: Bisakah Anda menyelesaikannya dalam O (n) kompleksitas waktu dan O (1) kompleksitas ruang tambahan?
sumber
Jawaban:
Python 2 , 34 byte
O (n 2 ) waktu, O (n) ruang
Disimpan 3 byte berkat @vaultah, dan 3 lainnya dari @xnor!
Cobalah online!
sumber
lambda l:l[map(l.remove,set(l))<0]
bekerja, meskipun urutan evaluasi aneh.-1
ketika tidak ada duplikat ditemukan tanpa 'kode footer', apakah kode itu tidak dihitung terhadap byte? Saya baru mengenal kode golf, maaf jika ini pertanyaan mendasar!JavaScript (ES6),
47363125 byteDisimpan 6 byte berkat ThePirateBay
Kembali
undefined
jika tidak ada solusi.Kompleksitas waktu: O (n) :-)
Kompleksitas ruang: O (n) :-(
Bagaimana?
Kami melacak nilai-nilai yang sudah dihadapi oleh menyimpannya sebagai baru sifat asli array yang satu dengan menggunakan angka negatif. Dengan cara ini, mereka tidak dapat mengganggu entri asli.
Demo
Tampilkan cuplikan kode
sumber
a=>a.find(c=>!(a[-c]^=1))
Mathematica, 24 byte
Kemampuan mencocokkan pola Mathematica sangat keren!
Mengembalikan yang asli
List
untuk input yang tidak valid.Penjelasan
Di input, ganti ...
A
List
dengan elemen duplikat, dengan 0 atau lebih elemen sebelum, di antara, dan setelah duplikat ...Dengan elemen duplikat.
sumber
Jelly , 5 byte
Cobalah online!
Bagaimana itu bekerja
sumber
œ-
menghapus kejadian paling kanan? TIL-1
tanpa duplikat. Melempar pengecualian tidak apa-apa sesuai OP tapi saya tidak yakin apakah0
itu meskipun tidak dalam kisaran.Haskell , 35 byte
Cobalah online!Gangguan jika tidak ada duplikat ditemukan.
sumber
Jeli , 6 byte
Cobalah online!
Mengembalikan duplikat pertama, atau 0 jika tidak ada duplikat.
Penjelasan
sumber
ŒQi0ị
.i0
akan mengembalikan 0, di manaị
akan mengindeks dan mengembalikan nilai terakhir dari input bukannya 0.Japt , 7 byte
Uji secara online!
Penjelasan
Kalau tidak:
Uji secara online!
Penjelasan
sumber
Pyth, 5 byte
Suite uji
Hapus dari Q tampilan pertama setiap elemen di Q, lalu kembalikan elemen pertama.
sumber
Dyalog APL,
27242019131211 byteSekarang dimodifikasi untuk tidak bergantung pada v16! Cobalah online!
Bagaimana? (Dengan input N )
⊢⊃⍨...
- N pada indeks ini:⍴↑∪
- N dengan duplikat dihapus, kanan-empuk dengan0
agar sesuai N⊢=
- Kesetaraan elemen-bijaksana dengan N0⍳⍨
- Indeks yang pertama0
. `sumber
⎕AV
, kan?⎕U2378
saat memuat. Cobalah online!Python 3 ,
9492 byteO (n) waktu dan O (1) memori ekstra.
Cobalah online!
Sumber algoritme .
Penjelasan
Ide dasar dari algoritma ini adalah untuk berjalan melalui setiap elemen dari kiri ke kanan, melacak nomor yang telah muncul, dan mengembalikan angka setelah mencapai angka yang telah muncul, dan mengembalikan -1 setelah melintasi setiap elemen.
Namun, ini menggunakan cara pintar untuk menyimpan angka yang muncul tanpa menggunakan memori ekstra: untuk menyimpannya sebagai tanda elemen yang diindeks oleh angka. Sebagai contoh, saya dapat mewakili fakta bahwa
2
dan3
sudah muncul dengan memilikia[2]
dana[3]
negatif, jika array 1-diindeks.sumber
i
mana [i]> n?1
a.length tetapi untuk [i] = a.length tidakkah ini akan keluar dari batas?t=abs(a[i])-1=a.length-1
Perl 6 , 13 byte
Cobalah
Penjelasan
Ini
*
dalam posisi Term sehingga seluruh pernyataan adalah lambda Apapun Kode.Ini
.repeated
adalah metode yang menghasilkan setiap nilai kecuali untuk pertama kalinya setiap nilai terlihat.[0]
hanya mengembalikan nilai pertama dalam Seq .Jika tidak ada nilai, Nil dikembalikan.
( Nil adalah basis dari tipe-tipe Kegagalan , dan semua tipe adalah nilainya sendiri yang tidak ditentukan, jadi Nihil berbeda dari nilai yang tidak ditentukan dalam kebanyakan bahasa lain)
Perhatikan bahwa sejak implementasi
.repeated
menghasilkan Seq itu berarti tidak mulai melakukan pekerjaan apa pun sampai Anda meminta nilai, dan itu hanya bekerja cukup untuk menghasilkan apa yang Anda minta.Jadi akan mudah untuk berpendapat bahwa ini memiliki kompleksitas waktu O (n) terburuk , dan pada kompleksitas waktu O (2) terbaik jika nilai kedua adalah pengulangan dari yang pertama.
Serupa mungkin dapat dikatakan kompleksitas memori.
sumber
APL (Dyalog) , 20 byte
Cobalah online!
2⍴¯1
negatif satu r eshaped ke dalam daftar panjang-dua⎕,
dapatkan input (mnemonic: kotak konsol) dan tambahkan itun←
simpan itu di n,\
awalan dari n (rangkaian gabungan kumulatif)(
...)¨
terapkan fungsi diam-diam berikut untuk setiap awalan,
adalah ravel (hanya memastikan bahwa awalan adalah daftar)≢
berbeda dari∪
elemen unik [?] (yaitu apakah awalan memiliki duplikat?)n/⍨
gunakan itu untuk memfilter n (menghapus semua elemen hingga yang pertama ditemukan duplikatnya)⊃
pilih elemen pertama dari itusumber
APL (Dyalog) , 11 byte
Sesuai aturan baru , melempar kesalahan jika tidak ada duplikat.
Cobalah online!
⍳⍨
indeks kemunculan pertama setiap elemen~
dihapus dari⍳∘≢
dari semua indeks⍬⍴
membentuk kembali itu menjadi skalar (memberikan nol jika tidak ada data tersedia)⊃⍨
gunakan itu untuk memilih (memberikan kesalahan pada nol)⊢
argumensumber
APL, 15
Sepertinya kita dapat mengembalikan 0 bukannya -1 ketika tidak ada duplikat, (terima kasih Adám atas komentarnya). Jadi 3 byte lebih sedikit.
Sedikit deskripsi:
Untuk referensi, solusi lama menambahkan -1 ke daftar di akhir, jadi jika daftar berakhir kosong, itu akan mengandung -1 dan elemen pertama adalah -1.
Cobalah di tryapl.org
sumber
¯1
, demikian juga{⊃⍵[(⍳⍴⍵)~⍵⍳⍵]}
seharusnya.Retina ,
2624 byteCobalah online! Penjelasan:
\b(\d+)\b
cocok dengan masing-masing angka secara bergantian, dan kemudian tampilan di belakang terlihat untuk melihat apakah nomor tersebut merupakan duplikat; jika itu1
pertandingan st adalah!
output, bukan jumlah pertandingan. Sayangnya menempatkan tampilan di belakang tampaknya tidak berfungsi, jika tidak maka akan menghemat beberapa byte. Sunting:Menambahkan 7 byte untuk mematuhi nilaiDisimpan 2 byte berkat @MartinEnder.-1
pengembalian tanpa kecocokan.sumber
-1
.MATL , 8 byte
Memberikan kesalahan (tanpa output) jika tidak ada duplikat.
Coba di MATL Online!
Penjelasan
sumber
R, 34 byte
Potong beberapa karakter dari jawaban dari @djhurio, meskipun tidak memiliki reputasi yang cukup untuk berkomentar.
sumber
-1
tetapi dengan spec baru, saya berhasil menurunkannya lebih jauh. Ini masih solid dan ini pendekatan yang berbeda dari cara dia melakukannya, jadi saya akan memberi Anda +1!J,
1716 byteBagaimana?
sumber
R , 28 byte
Cobalah online!
sumber
NA
untuk nilai yang hilang karena spek telah berubah; jadi(x=scan())[duplicated(x)][1]
sangat valid.J , 12 byte
Cobalah online!
Penjelasan
sumber
Dyalog APL Classic, 18 karakter
Hanya bekerja di
⎕IO←0
.Hapus dari daftar indeks elemen-elemen argumen dengan "-1" daftar indeks dari nubnya dan kemudian pilih yang pertama dari yang tersisa. Jika setelah penghapusan hanya ada vektor kosong, elemen pertamanya adalah dengan definisi 0 yang digunakan untuk mengindeks argumen yang diperluas menghasilkan -1 yang diinginkan.
sumber
¯1
, sehingga Anda dapat menghapus¯1,
dan menggunakan⎕IO←1
.Ruby ,
2836 byteSalah memahami tantangan pertama kali.
O(n)
waktu,O(n)
ruang.Cobalah online!
sumber
Java (OpenJDK 8) ,
65117109 byteSolusi 65 byte sebelumnya:
Solusi baru. 19 byte termasuk untuk
import java.math.*;
-8 byte berkat @Nevay
Cobalah online!
Edit
Algoritme dalam program asli saya baik-baik saja, tetapi ukuran statis dari tipe data yang digunakan berarti bahwa itu pecah cukup cepat setelah ukurannya pergi di atas ambang batas tertentu.
Saya telah mengubah tipe data yang digunakan dalam perhitungan untuk meningkatkan batas memori program untuk mengakomodasi ini (digunakan
BigInteger
untuk presisi sewenang-wenang alih-alihint
ataulong
). Namun, ini membuatnya diperdebatkan apakah ini dianggap sebagaiO(1)
kompleksitas ruang atau tidak .Saya akan membiarkan penjelasan saya di bawah ini tetap utuh, tetapi saya ingin menambahkan bahwa sekarang saya percaya tidak mungkin mencapai
O(1)
kompleksitas ruang tanpa membuat beberapa asumsi.Bukti
Tentukan
N
sebagai bilangan bulat sedemikian rupa sehingga2 <= N
.Membiarkan
S
menjadi daftar yang mewakili serangkaian bilangan bulat acak[x{1}, ..., x{N}]
, di manax{i}
memiliki kendala1 <= x{i} <= N
.Kompleksitas waktu (dalam notasi O-Besar) yang diperlukan untuk beralih melalui daftar ini tepat sekali per elemen
O(n)
Tantangan yang diberikan adalah menemukan nilai duplikat pertama dalam daftar. Lebih khusus lagi, kami sedang mencari nilai pertama
S
yang merupakan duplikat dari item sebelumnya dalam daftar.Biarkan
p
danq
jadilah posisi dua elemen dalam daftar sedemikian rupa sehinggap < q
danx{p} == x{q}
. Tantangan kita menjadi menemukan yang terkecilq
yang memenuhi kondisi tersebut.Pendekatan yang jelas untuk masalah ini adalah untuk beralih melalui S dan memeriksa apakah kami
x{i}
ada di daftar lainT
: Jikax{i}
tidak adaT
, kami menyimpannya diT
. Jikax{i}
adaT
, itu adalah nilai duplikat pertama dan oleh karena itu yang terkecilq
, dan karena itu kami mengembalikannya. Efisiensi ruang iniO(n)
.Untuk mencapai
O(1)
kompleksitas ruang sambil mempertahankanO(n)
kompleksitas waktu, kita harus menyimpan informasi unik tentang setiap objek dalam daftar dalam jumlah ruang terbatas. Karena itu, satu-satunya cara algoritma dapat bekerjaO(1)
kompleksitas ruang adalah jika: 1. N diberi batas atas yang sesuai dengan memori yang diperlukan untuk menyimpan jumlah maksimum dari nilai yang mungkin untuk tipe data terbatas tertentu. 2. Penugasan ulang variabel tidak berubah tunggal dihitung terhadap kompleksitas, hanya jumlah variabel (daftar menjadi beberapa variabel). 3. (Berdasarkan jawaban lain) Daftar ini (atau setidaknya, elemen-elemen dari daftar) dapat berubah, dan tipe data dari daftar tersebut telah ditetapkan sebagai bilangan bulat yang ditandatangani, memungkinkan untuk perubahan dilakukan pada elemen lebih jauh dalam daftar. tanpa menggunakan memori tambahan.1 dan 3 keduanya membutuhkan asumsi dan spesifikasi tentang tipe data, sementara 2 mensyaratkan bahwa hanya jumlah variabel yang dipertimbangkan untuk perhitungan kompleksitas ruang, daripada ukuran variabel-variabel tersebut. Jika tidak ada asumsi ini yang diterima, mustahil untuk mencapai
O(n)
kompleksitas waktu dan jugaO(1)
kompleksitas ruang.Penjelasan
Whoo boy, yang ini butuh
waktu lama untuk memikirkansedikit kekuatan otak.Jadi, mencari bonus itu sulit. Kita perlu keduanya beroperasi di atas seluruh daftar tepat satu kali dan melacak nilai mana yang sudah kita iterasi tanpa kompleksitas ruang tambahan.
Manipulasi bit memecahkan masalah tersebut. Kami menginisialisasi
O(1)
'penyimpanan' kami, sepasang bilangan bulat, lalu iterate melalui daftar, ATAU-bit engan di integer pertama kami dan menyimpan hasil itu ke yang kedua.Misalnya, jika sudah
1101
, dan kami melakukan operasi ATAU10
, kami dapat1111
. Jika kita melakukan ATAU dengan yang lain10
, kita masih punya1101
.Ergo, setelah kami melakukan operasi ATAU dan berakhir dengan nomor yang sama, kami telah menemukan duplikat kami. Tidak ada duplikat dalam array yang menyebabkan program untuk menjalankan dan melemparkan pengecualian.
sumber
PHP,
56 44 3832 byteJalankan seperti ini:
Penjelasan
Tweaks
Kompleksitas
Seperti dapat dilihat dari versi kode yang dikomentari, kompleksitas waktu adalah linier
O(n)
. Dalam hal memori, maksimumn+1
variabel akan ditetapkan. Jadi begituO(n)
.sumber
error_reporting
opsi ke jumlah byte (atau gunakan-n
, yang gratis)./dev/null
, yang sama.O(1)
untuk ruang tambahan? Anda benar-benar menugaskan variabel baru pern
, yaituO(n)
Java 8,
827876 bytesTidak lagi layak,756764 bytes di bawah ini di editSebagai fungsi lambda:
Mungkin bisa dibuat lebih kecil, ini sangat cepat.
Penjelasan:
* Edit *
756764 byte menggunakan strategi negasi:Cobalah online!
(-3 byte berkat @Nevay)
Penjelasan:
Loops atas array, meniadakan untuk melacak. Jika tidak ada dupes, cukup jalankan dan lemparkan kesalahan.
Keduanya bekerja pada kompleksitas ruang O (n) dan O (n).
sumber
Number
, karenai
ini adalahlong
dan-1
adalahint
.long
, tetapi tidakLong
seperti yang diperlukan untuk lambda ditugaskan ke aFunction
. Apakah Anda mengujinya? Apapun, solusi itu bisa diganti dengan yang baru.Set s=new HashSet();
untuk menghemat 7 byte. (Selain itu: afaik imporjava.util.*;
harus dimasukkan ke dalam jumlah byte -> +19 byte.) Pernyataan pengembalian dapat berupareturn++j
, jika-pernyataan dapat dihapusa->{int i=0,j;for(;(a[j=Math.abs(a[i++])-1]*=-1)<0;);return++j;}
(-3 byte).Brachylog , 5 byte
Cobalah online!
Penjelasan
Adfix built-in
a
berisi daftar pertama semua awalan dalam peningkatan urutan panjang, kemudian sufiks dengan penurunan urutan panjang. Dengan demikian output dihasilkan oleh awalan terpendek yang memungkinkannya, jika ada. Jika awalan tidak memiliki duplikat, sisa program gagal untuk itu, karena setiap urutan elemen yang sama memiliki panjang 1, dan elemen pertama dari ekornya tidak ada. Jika awalan memiliki elemen yang diulang, kita dapat memilih urutan panjang-2 yang mengandung keduanya, dan program mengembalikan yang terakhir.sumber
a⊇Ċ=h
yang hanya terlihat pada panjang-2 himpunan bagian.C #, 145 byte
Mungkin cara yang jauh lebih pendek untuk melakukan ini di C # dengan loop sederhana tapi saya ingin mencobanya dengan Linq.
Cobalah online!
Versi Lengkap / Terformat:
sumber
Haskell ,
7869 byteCobalah online!
Disimpan 9 byte berkat @nimi
Jalur dasar melalui daftar. Jika elemen saat ini belum terlihat (
i<0
) dan ada di daftar akumulator (elem x a
) maka simpan indeks saat ini. Lain, pertahankan indeks -1. Bagaimanapun, tambahkan elemen saat ini ke daftar akumulator.EDIT : Saya tidak cukup membaca pertanyaan: kode ini menampilkan indeks dari elemen kedua dari elemen duplikat.
sumber
\ ... ->(last$i:[j|i<0,elem x a],x:a)
. Juga: tidak perlu untuk ituf=
, karena fungsi yang tidak disebutkan namanya diizinkan.Python 2,
7165 byteKembali
None
jika tidak ada elemen duplikatEdit: -6 byte terima kasih kepada @ musicman523
Cobalah online!
O (n) kompleksitas waktu, O (n) kompleksitas ruang, O (1) ruang tambahan.
Karena daftar input menggunakan O (n) spasi, kompleksitas ruang terikat oleh ini. Artinya kita tidak dapat memiliki kompleksitas ruang yang lebih rendah daripada O (n)
Memodifikasi daftar asli, jika ini tidak diizinkan, kami dapat melakukannya dalam kompleksitas yang sama dengan 129 byte
Penjelasan
Karena setiap elemen lebih besar dari 0 dan kurang dari atau sama dengan ukuran daftar, daftar memiliki untuk setiap elemen a, elemen pada indeks a - 1 (0 diindeks). Kami mengeksploitasi ini dengan mengatakan bahwa jika elemen pada indeks i negatif, kami telah melihatnya sebelumnya.
Untuk setiap elemen a dalam daftar n, kami membiarkan Anda menjadi negatif nilai absolut a. (Kita membiarkannya negatif karena python dapat mengindeks daftar dengan indeks negatif, dan jika tidak kita perlu melakukannya
u=abs(a)-1
) Jika elemen pada indeks u dalam daftar adalah negatif, kita telah melihatnya sebelumnya dan karenanya dapat mengembalikan -u (untuk mendapatkan nilai absolut a, karena semua elemen positif) . Jika tidak, kita menetapkan elemen pada indeks u menjadi negatif, untuk mengingat bahwa kita telah melihat elemen nilai sebelumnya.sumber
1
dann
, seperti bagaimana itu diberikan, maka jelas tidak berfungsi.Jelly , 4 byte
Cobalah online!
Jika semua elemen unik, ini akan kembali
0
(perilaku tidak terdefinisi).sumber