Temukan elemen duplikat pertama

39

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 , jadi jawaban tersingkat dalam byte menang.

BONUS: Bisakah Anda menyelesaikannya dalam O (n) kompleksitas waktu dan O (1) kompleksitas ruang tambahan?

Jeanderson Candido
sumber
Komentar bukan untuk diskusi panjang; percakapan ini telah dipindahkan ke obrolan .
Martin Ender

Jawaban:

15

Python 2 , 34 byte

O (n 2 ) waktu, O (n) ruang

Disimpan 3 byte berkat @vaultah, dan 3 lainnya dari @xnor!

lambda l:l[map(l.remove,set(l))<0]

Cobalah online!

musicman523
sumber
1
Sepertinya lambda l:l[map(l.remove,set(l))<0]bekerja, meskipun urutan evaluasi aneh.
xnor
Ini tidak kembali -1ketika tidak ada duplikat ditemukan tanpa 'kode footer', apakah kode itu tidak dihitung terhadap byte? Saya baru mengenal kode golf, maaf jika ini pertanyaan mendasar!
Chris_Rands
@Chris_Rands Di bawah pertanyaan, musisi bertanya apakah pengecualian baik-baik saja, bukan -1 dan OP mengatakan tidak apa-apa dan jawaban musisi melemparkan pengecualian.
LiefdeWen
Butuh beberapa saat untuk mencari tahu. Permainan yang bagus. Mendapatkan elemen 0 dari l menggunakan kondisional setelah memodifikasi itu benar-benar pintar.
Thoth19
Apakah Python menjamin kompleksitas ruang dan waktu dari fungsi-fungsi pustaka standar seperti set.remove?
Draconis
11

JavaScript (ES6), 47 36 31 25 byte

Disimpan 6 byte berkat ThePirateBay

Kembali undefinedjika tidak ada solusi.

Kompleksitas waktu: O (n) :-)
Kompleksitas ruang: O (n) :-(

a=>a.find(c=>!(a[-c]^=1))

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

Arnauld
sumber
25 byte:a=>a.find(c=>!(a[-c]^=1))
@ThePirateBay Oh, tentu saja. Terima kasih!
Arnauld
Hanya perhatikan bahwa Objek dalam JavaScript mungkin tidak diimplementasikan sebagai tabel hash. Kompleksitas waktu dalam mengakses kunci beberapa objek mungkin bukan O (1).
tsh
6

Mathematica, 24 byte

#/.{h=___,a_,h,a_,h}:>a&

Kemampuan mencocokkan pola Mathematica sangat keren!

Mengembalikan yang asli Listuntuk input yang tidak valid.

Penjelasan

#/.

Di input, ganti ...

{h=___,a_,h,a_,h}

A Listdengan elemen duplikat, dengan 0 atau lebih elemen sebelum, di antara, dan setelah duplikat ...

... :>a

Dengan elemen duplikat.

JungHwan Min
sumber
6

Jelly , 5 byte

Ṛœ-QṪ

Cobalah online!

Bagaimana itu bekerja

Ṛœ-QṪ  Main link. Argument: A (array)

Ṛ      Yield A, reversed.
   Q   Unique; yield A, deduplicated.
 œ-    Perform multiset subtraction.
       This removes the rightmost occurrence of each unique element from reversed
       A, which corresponds to the leftmost occurrence in A.
    Ṫ  Take; take the rightmost remaining element, i.e., the first duplicate of A.
Dennis
sumber
œ-menghapus kejadian paling kanan? TIL
Erik the Outgolfer
Ini sepertinya tidak kembali -1tanpa duplikat. Melempar pengecualian tidak apa-apa sesuai OP tapi saya tidak yakin apakah 0itu meskipun tidak dalam kisaran.
Erik the Outgolfer
4

Jeli , 6 byte

xŒQ¬$Ḣ

Cobalah online!

Mengembalikan duplikat pertama, atau 0 jika tidak ada duplikat.

Penjelasan

xŒQ¬$Ḣ  Input: array M
    $   Operate on M
 ŒQ       Distinct sieve - Returns a boolean mask where an index is truthy
          for the first occurrence of an element
   ¬      Logical NOT
x       Copy each value in M that many times
     Ḣ  Head
mil
sumber
Ini Golfier untuk penggunaan pengindeksan seperti ini: ŒQi0ị.
Erik the Outgolfer
@EriktheOutgolfer Jika tidak ada duplikat, i0akan mengembalikan 0, di mana akan mengindeks dan mengembalikan nilai terakhir dari input bukannya 0.
mil
4

Japt , 7 byte

æ@bX ¦Y

Uji secara online!

Penjelasan

 æ@   bX ¦ Y
UæXY{UbX !=Y}  Ungolfed
               Implicit: U = input array
UæXY{       }  Return the first item X (at index Y) in U where
     UbX         the first index of X in U
         !=Y     is not equal to Y.
               In other words, find the first item which has already occured.
               Implicit: output result of last expression

Kalau tidak:

æ@¯Y øX

Uji secara online!

Penjelasan

 æ@   ¯ Y øX
UæXY{Us0Y øX}  Ungolfed
               Implicit: U = input array
UæXY{       }  Return the first item X (at index Y) in U where
     Us0Y        the first Y items of U (literally U.slice(0, Y))
          øX     contains X.
               In other words, find the first item which has already occured.
               Implicit: output result of last expression
Produksi ETH
sumber
4

Pyth, 5 byte

h.-Q{

Suite uji

Hapus dari Q tampilan pertama setiap elemen di Q, lalu kembalikan elemen pertama.

isaacg
sumber
@LuisMendo Ok terima kasih. Maaf karena membuat kebingungan, saya harus belajar membaca ...
Tn. Xcoder
@ Mr.Xcoder Tidak, ini salah OP. Informasi itu harus ada dalam teks tantangan, tetapi hanya dalam komentar
Luis Mendo
4

Dyalog APL, 27 24 20 19 13 12 11 byte

⊢⊃⍨0⍳⍨⊢=⍴↑∪

Sekarang dimodifikasi untuk tidak bergantung pada v16! Cobalah online!

Bagaimana? (Dengan input N )

  • ⊢⊃⍨...- N pada indeks ini:
    • ⍴↑∪- N dengan duplikat dihapus, kanan-empuk dengan 0agar sesuai N
    • ⊢=- Kesetaraan elemen-bijaksana dengan N
    • 0⍳⍨- Indeks yang pertama 0. `
Zacharý
sumber
tidak masalah, saya salah membaca pertanyaan. uji kasus tidak cukup ...
Uriel
Maaf telah menyesatkan Anda, saya juga salah membaca pertanyaan.
mil
Sepertinya saya 36 byte.
Adám
Ya Tuhan, iota underbar tidak ada ⎕AV, kan?
Zacharý
@ Zacharý Right, Classic menerjemahkannya ke ⎕U2378 saat memuat. Cobalah online!
Adám
3

Python 3 , 94 92 byte

O (n) waktu dan O (1) memori ekstra.

def f(a):
 r=-1
 for i in range(len(a)):t=abs(a[i])-1;r=[r,i+1][a[t]<0>r];a[t]*=-1
 return r

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 2dan 3sudah muncul dengan memiliki a[2]dan a[3]negatif, jika array 1-diindeks.

Biarawati Bocor
sumber
Apa yang akan dilakukan di imana [i]> n?
Downgoat
@Downgoat membaca pertanyaan itu lagi.
Leaky Nun
Pertanyaannya mengatakan 1a.length tetapi untuk [i] = a.length tidakkah ini akan keluar dari batas?
Downgoat
@Downgoatt=abs(a[i])-1=a.length-1
Leaky Nun
3

Perl 6 , 13 byte

*.repeated[0]

Cobalah


Penjelasan

  • Ini *dalam posisi Term sehingga seluruh pernyataan adalah lambda Apapun Kode.

  • Ini .repeatedadalah metode yang menghasilkan setiap nilai kecuali untuk pertama kalinya setiap nilai terlihat.

    say [2, 3, 3, 3, 1, 5, 2, 3].repeated.perl; # (3, 3, 2, 3).Seq
    #   (      3, 3,       2, 3).Seq
  • [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.

Brad Gilbert b2gills
sumber
3

APL (Dyalog) , 20 byte

n/⍨(,≢∪)¨,\n←⎕,2⍴¯1

Cobalah online!

2⍴¯1 negatif satu r eshaped ke dalam daftar panjang-dua

⎕, dapatkan input (mnemonic: kotak konsol) dan tambahkan itu

n← 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 itu

Adám
sumber
Wow, kamu dikalahkan tiga kali. Tetap, +1. Dan bisakah Anda menambahkan penjelasan tentang cara kerjanya?
Zacharý
@ Zacharý Tampaknya saya hanya perlu membuat bola bergulir. Ini dia
Adám
@ Zacharý Akhirnya, saya berhasil mengalahkan mereka semua .
Adám
3

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)

 argumen

Adám
sumber
Ya, ketika peraturan diubah, tentu saja Anda bisa mengalahkan semuanya!
Zacharý
Yah, aku mengikatmu.
Zacharý
3

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:

⍵⍳⍵         search the argument in itself: returns for  each element the index of it's first occurrence
(⍳⍴⍵)~⍵⍳⍵   create a list of all indexes, remove those found in ⍵⍳⍵; i.e. remove all first elements
⊃⍵[...]     of all remaining elements, take the first. If the array is empty, APL returns zero

Untuk referensi, solusi lama menambahkan -1 ke daftar di akhir, jadi jika daftar berakhir kosong, itu akan mengandung -1 dan elemen pertama adalah -1.

{⊃⍵[(⍳⍴⍵)~⍵⍳⍵],¯1}

Cobalah di tryapl.org

Moris Zucca
sumber
Anda dapat mengembalikan nol alih-alih¯1 , demikian juga {⊃⍵[(⍳⍴⍵)~⍵⍳⍵]}seharusnya.
Adám
3

Retina , 26 24 byte

1!`\b(\d+)\b(?<=\b\1 .*)

Cobalah online! Penjelasan: \b(\d+)\bcocok dengan masing-masing angka secara bergantian, dan kemudian tampilan di belakang terlihat untuk melihat apakah nomor tersebut merupakan duplikat; jika itu 1pertandingan 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 nilai -1pengembalian tanpa kecocokan. Disimpan 2 byte berkat @MartinEnder.

Neil
sumber
2
Sebagai catatan, lookaround tidak akan mundur. Ini mencegah ini dari bekerja jika Anda mencoba untuk meletakkannya sebelumnya. Saya telah membuat kesalahan ini berkali-kali, dan Martin selalu mengoreksi saya.
FryAmTheEggman
Saya mendapat 30 byte dengan menggunakan lookahead bukan lookbehind. Juga, peraturan sekarang mengatakan Anda tidak perlu kembali -1.
Value Ink
@ ValueInk Tetapi jawaban yang benar untuk test case adalah 3 ...
Neil
OH. Saya salah membaca tantangan, ups
Value Ink
2

MATL , 8 byte

&=Rsqf1)

Memberikan kesalahan (tanpa output) jika tidak ada duplikat.

Coba di MATL Online!

Penjelasan

&=   % Implict input. Matrix of all pairwise equality comparisons
R    % Keep the upper triangular part (i.e. set lower part to false)
s    % Sum of each column
q    % Subtract 1
f    % Indices of nonzero values
1)   % Get first. Gives an error is there is none. Implictly display
Luis Mendo
sumber
2

R, 34 byte

c((x=scan())[duplicated(x)],-1)[1]

Potong beberapa karakter dari jawaban dari @djhurio, meskipun tidak memiliki reputasi yang cukup untuk berkomentar.

RoryT
sumber
oh ... saya tidak melihat jawaban ini; ini bagus untuk spec sebelumnya ketika nilai-nilai yang hilang diperlukan -1tetapi 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!
Giuseppe
2

J, 17 16 byte

(*/{_1,~i.&0)@~:

Bagaimana?

(*/{_1,~i.&0)@~:

             @~: returns the nub sieve which is a vector with 1 for the first occurrence of an element in the argument and 0 otherwise

        i.&0     returns the first index of duplication

    _1,~         appends _1 to the index

 */              returns 0 with duplicates (product across nub sieve)

     {           select _1 if no duplicates, otherwise return the index
bob
sumber
2

R , 28 byte

(x=scan())[duplicated(x)][1]

Cobalah online!

djhurio
sumber
Saya pikir Anda sekarang dapat kembali NAuntuk nilai yang hilang karena spek telah berubah; jadi (x=scan())[duplicated(x)][1]sangat valid.
Giuseppe
2

J , 12 byte

,&_1{~~:i.0:

Cobalah online!

Penjelasan

,&_1{~~:i.0:  Input: array M
      ~:      Nub-sieve
          0:  The constant 0
        i.    Find the index of the first occurrence of 0 (the first duplicate)
,&_1          Append -1 to M
    {~        Select the value from the previous at the index of the first duplicate
mil
sumber
2

Dyalog APL Classic, 18 karakter

Hanya bekerja di ⎕IO←0.

     w[⊃(⍳∘≢~⍳⍨)w←¯1,⎕]

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.

lstefano
sumber
Um ... ada apa dengan spasi acak acak? +1 untuk mengalahkan saya dengan satu byte.
Zacharý
Anda dapat melakukan kesalahan alih-alih kembali¯1 , sehingga Anda dapat menghapus ¯1,dan menggunakan ⎕IO←1.
Adám
2

Ruby , 28 36 byte

Salah memahami tantangan pertama kali. O(n)waktu, O(n)ruang.

->a{d={};a.find{|e|b=d[e];d[e]=1;b}}

Cobalah online!

Nilai Tinta
sumber
2

Java (OpenJDK 8) , 65 117 109 byte

Solusi 65 byte sebelumnya:

r->{for(int a,b=0,z,i=0;;b=a)if((a=b|1<<(z=r[i++]))==b)return z;}

Solusi baru. 19 byte termasuk untukimport java.math.*;

-8 byte berkat @Nevay

r->{int z,i=0;for(BigInteger c=BigInteger.ZERO;c.min(c=c.setBit(z=r[i++]))!=c;);return z;}

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 BigIntegeruntuk presisi sewenang-wenang alih-alih intatau long). Namun, ini membuatnya diperdebatkan apakah ini dianggap sebagai O(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 Nsebagai bilangan bulat sedemikian rupa sehingga 2 <= N.

Membiarkan Smenjadi daftar yang mewakili serangkaian bilangan bulat acak [x{1}, ..., x{N}], di mana x{i}memiliki kendala 1 <= 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 Syang merupakan duplikat dari item sebelumnya dalam daftar.

Biarkan pdan qjadilah posisi dua elemen dalam daftar sedemikian rupa sehingga p < qdan x{p} == x{q}. Tantangan kita menjadi menemukan yang terkecil qyang memenuhi kondisi tersebut.

Pendekatan yang jelas untuk masalah ini adalah untuk beralih melalui S dan memeriksa apakah kami x{i}ada di daftar lain T: Jika x{i}tidak ada T, kami menyimpannya di T. Jika x{i}ada T, itu adalah nilai duplikat pertama dan oleh karena itu yang terkecil q, dan karena itu kami mengembalikannya. Efisiensi ruang iniO(n) .

Untuk mencapai O(1)kompleksitas ruang sambil mempertahankan O(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 juga O(1)kompleksitas ruang.

Penjelasan

Whoo boy, yang ini butuh waktu lama untuk memikirkan sedikit 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 ATAU 10, kami dapat 1111. Jika kita melakukan ATAU dengan yang lain 10, kita masih punya 1101.

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.

Xanderhall
sumber
Juga, tes kedua Anda termasuk angka 100, tapi itu tidak mungkin karena array itu sendiri hanya 5 panjang
SchoolBoy
Juga, ini gagal karena sebuah int tidak memiliki cukup penyimpanan.
SchoolBoy
@ SchoolBoy Tangkapan yang bagus. Satu-satunya masalah saya adalah bahwa sepertinya tidak ada batas atas pada ukuran array, jadi saya tidak bisa secara realistis mengubah kode saya untuk menyelesaikan masalah memori.
Xanderhall
@Xanderhall Benar, tetapi saya merasa seperti 32 (atau jika Anda menggunakan, 64) angka terlalu sedikit: p. Either way, memaksakan batasan pada input, dan kemudian mengalokasikan memori maksimum yang dibutuhkan dan menyebutnya O (1) memori hanyalah cheat. Masih O (n) karena jika ukuran input meningkat, demikian juga ini terikat ke memori. Yang juga mengapa saya pikir tidak mungkin untuk membuat algoritma O (n) O (1)
SchoolBoy
@Xanderhall PS Saya semakin dekat dengan 65 Anda, saya di 67 byte: p
SchoolBoy
2

PHP, 56 44 38 32 byte

for(;!${$argv[++$x]}++;);echo$x;

Jalankan seperti ini:

php -nr 'for(;!${$argv[++$x]}++;);echo$x;' -- 2 3 3 1 5 2;echo
> 3

Penjelasan

for(
  ;
  !${                 // Loop until current value as a variable is truthy
    $argv[++$x]       // The item to check for is the next item from input
  }++;                // Post increment, the var is now truthy
);
echo $x;              // Echo the index of the duplicate.

Tweaks

  • Menyimpan 12 byte dengan menggunakan variabel, bukan array
  • Disimpan 6 byte dengan memanfaatkan aturan "perilaku tidak terdefinisi" untuk saat tidak ada kecocokan.
  • Disimpan 6 byte dengan menggunakan post-increment alih-alih pengaturan ke 1 setelah setiap loop

Kompleksitas

Seperti dapat dilihat dari versi kode yang dikomentari, kompleksitas waktu adalah linier O(n). Dalam hal memori, maksimum n+1variabel akan ditetapkan. Jadi begitu O(n).

aross
sumber
Terima kasih karena tidak menggunakan pengodean yang aneh. Tetapi Anda harus menambahkan error_reportingopsi ke jumlah byte (atau gunakan -n, yang gratis).
Titus
Kami sudah di sini sebelumnya. Pemberitahuan dan peringatan PHP diabaikan. Saya mungkin juga pipa mereka /dev/null, yang sama.
aross
Saya cenderung mengingat komentar yang salah. :) Bukankah ini O (n)?
Titus
Ya itu linier
aross
Bagaimana itu O(1)untuk ruang tambahan? Anda benar-benar menugaskan variabel baru per n, yaituO(n)
Xanderhall
2

Java 8, 82 78 76 bytes Tidak lagi layak, 75 67 64 bytes di bawah ini di edit

Sebagai fungsi lambda:

a->{Set<Long>s=new HashSet<>();for(long i:a)if(!s.add(i))return i;return-1;}

Mungkin bisa dibuat lebih kecil, ini sangat cepat.

Penjelasan:

a->{                                //New lambda function with 'a' as input
    Set<Long>s=new HashSet<>();     //New set
    for(long i:a)                   //Iterate over a
        if(!s.add(i))               //If can't add to s, already exists
            return i;               //Return current value
        return-1;                   //No dupes, return -1
}

* Edit *

75 67 64 byte menggunakan strategi negasi:

a->{int i=0,j;while((a[j=Math.abs(a[i++])-1]*=-1)<0);return++j;}

Cobalah online!

(-3 byte berkat @Nevay)

Penjelasan:

a->{                                         //New lambda expression with 'a' as input
    int i=0,j;                               //Initialise i and declare j
    while((a[j=Math.abs(a[i++])-1]*=-1)<0);  //Negate to keep track of current val until a negative is found
    return++j;                               //Return value
}

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

SchoolBoy
sumber
Perlu dicatat bahwa ini perlu ditugaskan ke lambda yang kembali Number, karena iini adalah longdan -1adalah int.
Jakob
@Jakob Tidak perlu, -1 menjadi int akan secara otomatis dilemparkan ke panjang tanpa secara eksplisit menentukan pemeran
SchoolBoy
Ini akan berlaku secara implisit untuk long, tetapi tidak Longseperti yang diperlukan untuk lambda ditugaskan ke a Function. Apakah Anda mengujinya? Apapun, solusi itu bisa diganti dengan yang baru.
Jakob
Anda dapat menggunakan jenis mentah Set s=new HashSet();untuk menghemat 7 byte. (Selain itu: afaik impor java.util.*;harus dimasukkan ke dalam jumlah byte -> +19 byte.) Pernyataan pengembalian dapat berupa return++j, jika-pernyataan dapat dihapus a->{int i=0,j;for(;(a[j=Math.abs(a[i++])-1]*=-1)<0;);return++j;}(-3 byte).
Nevay
2

Brachylog , 5 byte

a⊇=bh

Cobalah online!

Penjelasan

a⊇=bh  Input is a list.
a      There is an adfix (prefix or suffix) of the input
 ⊇     and a subsequence of that adfix
  =    whose elements are all equal.
   b   Drop its first element
    h  and output the first element of the rest.

Adfix built-in aberisi 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.

Zgarb
sumber
Solusi 5 byte lainnya:, a⊇Ċ=hyang hanya terlihat pada panjang-2 himpunan bagian.
Fatalkan
1

C #, 145 byte

using System.Linq;a=>{var d=a.Where(n=>a.Count(t=>t==n)>1);return d.Select((n,i)=>new{n,i}).FirstOrDefault(o=>d.Take(o.i).Contains(o.n))?.n??-1;}

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:

namespace System.Linq
{
    class P
    {
        static void Main()
        {
            Func<int[], int> f = a =>
            {
                var d = a.Where(n => a.Count(t => t == n) > 1);
                return d.Select((n, i) => new { n, i }).FirstOrDefault(o => d.Take(o.i).Contains(o.n))?.n ?? -1;
            };

            Console.WriteLine(f(new[] { 2, 3, 3, 1, 5, 2 }));
            Console.WriteLine(f(new[] { 2, 4, 3, 5, 1 }));

            Console.ReadLine();
        }
    }
}
TheLethalCoder
sumber
Ini adalah versi loop sederhana. Tapi saya lebih suka versi Linq.
LiefdeWen
@LiefdeWen Posting sebagai jawaban :) Meskipun saya biasanya suka Linq lebih baik juga :) Mungkin bisa lebih pendek dengan Linq tapi saya sekarang yakin.
TheLethalCoder
Nah, pertanyaan ini kelebihan penduduk dan saya lebih suka Anda mendapatkan suara untuk pertanyaan ini.
LiefdeWen
1

Haskell , 78 69 byte

 fst.foldl(\(i,a)(j,x)->(last$i:[j|i<0,elem x a],x:a))(-1,[]).zip[1..]

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

jferard
sumber
Anda dapat menggunakan "Conditional Shorter" dari kami "Tips untuk bermain golf di Haskell" : \ ... ->(last$i:[j|i<0,elem x a],x:a). Juga: tidak perlu untuk itu f=, karena fungsi yang tidak disebutkan namanya diizinkan.
nimi
@nimi terima kasih atas tipnya!
jferard
1

Python 2, 71 65 byte

Kembali None jika tidak ada elemen duplikat

Edit: -6 byte terima kasih kepada @ musicman523

def f(n):
 for a in n:
	u=-abs(a)
	if n[u]<0:return-u
	n[u]=-n[u]

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.

Halvard Hummel
sumber
Pekerjaan yang baik! 65 byte
musicman523
Apakah Anda yakin ini O (1) dalam memori? Anda masih menggunakan n bit memori untuk menyimpan nomor yang sudah dikunjungi, meskipun bitnya ada dalam tanda. Sepertinya saya ini O (n) yang menyamar
Wheat Wizard
Secara teknis ini menggunakan ruang O (n) - bit tanda n. Jika array hanya dapat menyimpan nilai di antara 1dan n, seperti bagaimana itu diberikan, maka jelas tidak berfungsi.
Oliver Ni
Ini benar-benar hanya sampai pada representasi yang Anda pilih untuk angka-angka. Jika nomor yang tidak ditandai digunakan, maka ini adalah ruang bantu O (n) . Jika nomor yang ditandatangani digunakan, maka bit tanda sudah ada, yang berarti O (1) ruang tambahan.
Halvard Hummel
Saya setuju dengan Anda di sana. Saya pribadi akan membiarkan Anda meluncur menggunakan bilangan bulat yang ditandatangani selama Anda tidak menggunakan bit tanda, itu harus tentang algoritma bukan teknis dari sistem. Yang sedang berkata saya pikir jika Anda akan menggunakan bit tanda Anda harus menghitungnya. Saya pikir jawaban ini cukup pintar. Jika ada suara yang tersisa hari ini saya akan memilihnya untuk melawan downvote.
Wheat Wizard
1

Jelly , 4 byte

ŒQi0

Cobalah online!

Jika semua elemen unik, ini akan kembali 0(perilaku tidak terdefinisi).

Erik the Outgolfer
sumber