Tulis sebuah program yang akan mengambil input 2 array integer dan mengembalikan nilai yang sebenarnya jika ada elemen yang ada di kedua array, atau yang salah sebaliknya. Solusi yang jelas untuk masalah ini adalah untuk beralih melalui setiap elemen dalam array pertama dan membandingkannya dengan masing-masing elemen dalam yang kedua, tetapi inilah masalahnya: Program Anda harus memiliki kompleksitas algoritme paling banyak, dalam kasus terburuk, O ( NlogN), di mana N adalah panjang array yang lebih panjang,

Kasus uji:

 {1,2,3,4,-5},{5,7,6,8} -> false
 {},{0}                 -> false
 {},{}                  -> false
 {1,2},{3,3}            -> false
 {3,2,1},{-4,3,5,6}     -> true
 {2,3},{2,2}            -> true

Ini adalah kode-golf , jadi kode terpendek dalam byte menang.

Sebenarnya 1 byte

∩

Cobalah online!

Ini hanyalah persimpangan yang ditetapkan bawaan. Nilai yang dihasilkan adalah persimpangan dari dua set - daftar yang tidak kosong (yang merupakan nilai kebenaran) jika ada persimpangan, dan daftar kosong (yang merupakan nilai falsey) sebaliknya.

Kompleksitas

Menurut Python Wiki , set persimpangan memiliki kompleksitas waktu terburuk O(N*M)(di mana Ndan Madalah panjang dari dua set). Namun, kompleksitas waktu hanya seburuk itu ketika dua set berisi objek berbeda yang semuanya memiliki nilai hash yang sama (misalnya, {"some string"} & {hash("some string")}). Karena elemen himpunan hanya bilangan bulat dalam kasus ini (dan tidak ada dua bilangan bulat yang memiliki nilai yang sama kecuali jika keduanya sama), kompleksitas kasus terburuk yang sebenarnya adalah O(min(N, M))(linear dalam panjang yang lebih kecil dari dua himpunan). Konstruksi setiap set adalah O(N)(linier dalam jumlah elemen), sehingga kompleksitas keseluruhannya O(max(N, M))(kompleksitas didominasi oleh konstruksi set yang lebih besar).

TSQL, 40 37 36 byte

SQL tidak memiliki array, melainkan menggunakan tabel

Mengembalikan -1 untuk true atau 0 untuk false

DECLARE @ table(a INT)
DECLARE @2 table(b INT)

INSERT @ values(1),(2),(3),(4),(-5)
INSERT @2 values(5),(6),(7),(8)

SELECT~-sign(min(abs(a-b)))FROM @,@2

Cobalah

Ruby, 37 byte:

exit ($*.map{|x|eval x}.reduce:&)!=[]

Seperti dalam definisi: "program yang akan mengambil input 2 array integer dan mengembalikan nilai kebenaran jika ...", ini adalah sebuah program, menerima 2 array sebagai string dalam input, mengembalikan benar atau salah.

sebagai fungsi - 14 byte:

->a,b{a&b!=[]}

Kompleksitas:

Dokumentasi ruby ​​dari operator itnersection (&) mengatakan "Ia membandingkan elemen menggunakan metode hash dan eql mereka untuk efisiensi.", Yang saya kira persis apa yang kita cari.

Secara empiris:

$ time ruby a.rb "[*1..1000001]" "[*1000001..2000000]"

real    0m0.375s
user    0m0.340s
sys 0m0.034s

$ time ruby a.rb "[*1..2000001]" "[*2000001..4000000]"

real    0m0.806s
user    0m0.772s
sys 0m0.032s

$ time ruby a.rb "[*1..4000001]" "[*4000001..8000000]"

real    0m1.932s
user    0m1.857s
sys 0m0.073s

$ time ruby a.rb "[*1..8000001]" "[*8000001..16000000]"

real    0m4.464s
user    0m4.336s
sys 0m0.119s

Yang sepertinya mengkonfirmasi itu.

Perl, 25 + 1 = 26 byte bekerja sama dengan Dada

print 2<($a{$_}|=$.)for@F

Jalankan dengan -a(penalti 1 byte).

Versi yang lebih baik dari program di bawah ini (yang disimpan untuk melihat sejarah solusi, dan untuk menunjukkan solusi yang saya temukan sendiri; ia juga memiliki lebih banyak penjelasan). The -apilihan berbunyi array ruang yang dipisahkan sebagai masukan, menyimpannya dalam @F. Kami menggunakan %akamus (diakses sebagai $a{$_}) untuk menyimpan bitmask di mana array input input berada, dan mencetak 1setiap kali kita melihat elemen di kedua array, yaitu nilai yang lebih tinggi dari 2 di dalam bitmask yang dihasilkan (untungnya, perbandingan pengembalian gagal string nol, jadi printtidak melakukan apa-apa). Kami tidak dapat menggunakan saykarena baris baru benar di Perl. Kinerja asimtotik sama dengan versi program yang lebih lama (tetapi lebih cepat dalam hal faktor konstan).

Perl, 44 + 1 = 45 byte

$a{"+$_"}|=$.for split}{$_={reverse%a}->{3}

Jalankan dengan -p(penalti 1 byte). Masukkan satu larik per baris, pisahkan elemen dengan spasi.

Ini bekerja melalui membuat tabel hash %ayang menyimpan bitmask dari array input yang nilainya telah terlihat. Jika terlihat di kedua array di baris 1 dan di baris 2, bitmask akan menyimpan nilai 3. Membalikkan nilai hash dan melihat apakah 3 memiliki kunci yang sesuai beri tahu kami jika ada nilai yang sama.

Kompleksitas dari algoritma ini adalah O (n) jika Anda menganggap pembuatan hash sebagai waktu yang konstan (yaitu, jika Anda memiliki bilangan bulat yang terikat, seperti Perl). Jika menggunakan bignum integer (yang bisa menjadi input ke dalam program ini, karena ia meninggalkan input sebagai string), kompleksitas algoritma itu sendiri secara nominal akan menjadi O (n log n) untuk setiap pembuatan hash, dan O (n) untuk pembalikan hash, yang menambahkan hingga O (n log n). Namun, algoritma hashing Perl mengalami potensi kinerja O (n²) dengan input yang dipilih secara jahat; algoritma ini diacak, untuk membuatnya tidak mungkin untuk menentukan apa input itu (dan mungkin itu tidak dapat dipicu hanya dengan integer), sehingga diperdebatkan dengan kelas kompleksitas apa yang "secara moral" diperhitungkan. Untungnya, ini tidak masalah jika ada

Kode ini akan berfungsi untuk input selain bilangan bulat, tetapi tidak akan berfungsi untuk lebih dari dua array (karena 3hardcode dan karena input pada baris ketiga tidak akan bitmask dengan benar, karena itu bukan kekuatan 2). Agak menyebalkan, kode secara alami mengembalikan salah satu elemen duplikat, yang benar dalam hampir semua kasus, tetapi "0"falsey dalam Perl dan elemen duplikat yang valid dalam array. Karena itu, saya harus menyia-nyiakan tiga byte yang bergantung +pada output, yang merupakan cara termurah yang saya temukan untuk memberikan output yang benar dalam kasus tepi array yang tumpang tindih 0. Jika saya diperbolehkan untuk menggunakan pengertian tentang truthy dan falsey dari bahasa lain selain Perl (di mana string tidak kosong adalah truthy), Anda dapat mengubah "+$_"untuk $_menyelamatkan tiga byte.

Python2 - 41 30 byte

lambda a,b:bool(set(a)&set(b))

Set persimpangan: O (min (N, M)) di mana N dan M adalah panjang set.

Konversi dari daftar ke set: O (maks (N, M))

• Terima kasih kepada Jakube karena telah menghemat 9 byte! set(a).intersection(b)->set(a)&set(b)
• Terima kasih kepada Kade karena telah menghemat 2 byte! -> dihapusf=

Aksioma, 439 byte

c:=0;s(x,y)==(free c;if x.1=%i and y.2=%i then(x.2<y.1=>return true;x.2>y.1=>return false;c:=1;return false);if x.2=%i and y.1=%i then(x.1<y.2=>return true;x.1>y.2=>return false;c:=1;return false);if x.1=%i and y.1=%i then(x.2<y.2=>return true;x.2>=y.2=>return false);if x.2=%i and y.2=%i then(x.1<y.1=>return true;x.1>=y.1=>return false);false);r(a,b)==(free c;c:=0;m:=[[%i,j] for j in a];n:=[[i,%i] for i in b];r:=merge(m,n);sort(s,r);c)

ini mengonversi daftar pertama dalam daftar sebagai [[i, 1], [i, 2] ...] daftar kedua dalam daftar sebagai [[1, i], [0, i] ...] di mana saya adalah variabel imajiner daripada menggabungkan daftar 2, dan membuat satu jenis yang akan menemukan jika ada satu elemen dari daftar 1 dalam daftar 2 sehingga akhirnya O (N log N) di mana N = daftar panjang 1 + daftar panjang 2

ungolfed

-- i get [0,0,1,2,3] and [0,4,6,7]  and build [[%i,0],[%i,0],[%i,1],[%i,2] [%i,3],[0,%i],..[7,%i]]
c:=0
s(x:List Complex INT,y:List Complex INT):Boolean==
  free c  -- [%i,n]<[n,%i]
  if x.1=%i and y.2=%i then
    x.2<y.1=> return true 
    x.2>y.1=> return false
    c:=1
    return false
  if x.2=%i and y.1=%i then
    x.1<y.2=>return true
    x.1>y.2=>return false
    c:=1
    return false
  if x.1=%i and y.1=%i then
    x.2< y.2=>return true
    x.2>=y.2=>return false
  if x.2=%i and y.2=%i then
    x.1< y.1=>return true
    x.1>=y.1=>return false
  false


r(a,b)==
  free c
  c:=0
  m:=[[%i, j]  for j in a]
  n:=[[ i,%i]  for i in b]
  r:=merge(m,n)
  sort(s, r)
  c

hasil

(12) -> r([1,2,3,4,-5], [5,7,6,8]), r([],[0]), r([],[]), r([1,2],[3,3]), r([3,2,1],[-4,3,5,6]), r([2,3],[2,2])
   Compiling function r with type (List PositiveInteger,List Integer)
       -> NonNegativeInteger
   Compiled code for r has been cleared.
   Compiled code for s has been cleared.
   Compiling function r with type (List PositiveInteger,List
  PositiveInteger) -> NonNegativeInteger
   Compiled code for r has been cleared.
   Compiling function s with type (List Complex Integer,List Complex
      Integer) -> Boolean
   Compiled code for s has been cleared.

   (12)  [0,0,0,0,1,1]
                                           Type: Tuple NonNegativeInteger

saya tidak mengerti mengapa itu "membersihkan" kode untuk r dan ...

PowerShell, 88 78 77 23 byte

!!(diff -Inc -Ex $A $B)

Terima kasih kepada @briantist karena telah memangkas 54 byte kekalahan dari jawaban asli saya, lebih banyak kata dengan mempersingkat -IncludeEqual , -ExcludeDifferentdan -Not!

if(-Not(diff -IncludeEqual -ExcludeDifferent $A $B)){("false")}else{("true")}

Saya tidak dapat menemukan sumber untuk Compare-Object( diffadalah alias untuk Compare-Object), jadi saya tidak yakin tentang kompleksitas waktu.

PHP , 15 byte

array_intersect

Cobalah online!

PHP built-in, sebagai fungsi callable / lambda. Return adalah nilai PHP truthy/ yang falseydapat diuji. Juga, sesuai dengan pengiriman PHP lainnya, implementasi ini harus memenuhi persyaratan kompleksitas tantangan ( StackExchange ).

R, 23 byte

sum(scan()%in%scan())>0

Jika kita berasumsi bahwa akan selalu ada satu dan hanya satu elemen yang cocok dan itu 1adalah nilai yang sebenarnya (yang ada di R ), maka kita dapat menulis:

sum(scan()%in%scan())

yaitu 21 byte.

PHP, 55 51 byte

<?=count(array_intersect($_GET[a],$_GET[b]))<1?0:1;

Penggunaan: simpan dalam file dan panggilan dari browser:

intersect.php?a[]=1&a[]=2&a[]=3&b[]=0&b[]=4&b[]=5output 0untuk false.

intersect.php?a[]=1&a[]=2&a[]=3&b[]=0&b[]=4&b[]=1output 1untuk true.

Tentang kompleksitas, saya tidak dapat menemukan referensi tetapi menurut posting StackOverflow ini skrip harus OK

GolfScript, 1 byte

Jika mengambil input secara langsung karena array pada stack diperbolehkan, solusi GolfScript satu byte ini harus memenuhi spesifikasi:

&

Jika I / O berbasis teks diperlukan, input harus dievaluasi terlebih dahulu, mendorong panjangnya hingga dua byte:

~&

Kedua solusi ini menggunakan operator persimpangan GolfScript array, yang diimplementasikan menggunakan operator yang sesuai di Ruby . Mereka mengembalikan array kosong (yang salah) jika array tidak mengandung elemen yang cocok, atau array yang tidak kosong (yang sebenarnya) berisi semua elemen yang cocok sebaliknya.

Sejauh ini saya belum dapat menemukan dokumentasi tentang implementasi internal atau kompleksitas asimptotik dari operator persimpangan Ruby array, di luar pernyataan singkat bahwa "Itu membandingkan elemen menggunakan hash dan eql? Metode mereka untuk efisiensi." Namun, implementasi yang masuk akal menggunakan tabel hash akan berjalan dalam waktu O ( n ) (dengan asumsi bahwa hashing dan perbandingan adalah O (1)), dan beberapa pengujian kinerja cepat menunjukkan bahwa ini memang masalahnya:

Tes ini dilakukan dengan menggunakan program GolfScript ~2?.2*,/&, yang mengambil integer k , menghasilkan urutan aritmatika elemen 2 × 2 ^k , membaginya menjadi dua array elemen 2 ^k dan menghitung persimpangan mereka (jelas kosong). Bintang merah menunjukkan waktu eksekusi terukur t dalam detik (pada skala logaritmik) untuk berbagai nilai k , sedangkan garis hijau memplot fungsi t = c × 2 ^k , di mana konstanta penskalaan c ≈ 2 ^−17.075 dipilih sebagai yang terbaik. sesuai dengan data yang diukur.

(Perhatikan bahwa, di sebidang log-log seperti ini, setiap fungsi polinomial dalam bentuk t = c × (2 ^k ) ^a akan menghasilkan garis lurus. Namun, kemiringan garis tergantung pada eksponen sebuah , dan data tentu konsisten dengan sebuah = 1 seperti yang ditunjukkan oleh garis hijau di atas. FWIW, numerik kecocokan eksponen untuk kumpulan data ini adalah sebuah ≈ 1,00789.)

JavaScript (ES6), 39 byte

(a,b,c=new Set(b))=>a.some(e=>c.has(e))

Akan lebih buruk dari O (n + m) tetapi mudah-mudahan tidak seburuk O (n * m).

Rust, 103 byte

|a:&[i32],b:&[i32]|!b.iter().collect::<std::collections::HashSet<_>>().is_disjoint(&a.iter().collect())

Mengambil dua irisan array (atau referensi ke array penuh, mereka merujuk ke irisan secara otomatis), menggabungkannya ke dalam set, dan memeriksa non-disjointness. Saya tidak begitu yakin bagaimana set union diimplementasikan di pustaka standar Rust, tetapi seharusnya O (n + m) paling buruk.

Tanpa menggunakan koleksi, alternatif termudah yang saya lihat adalah mengurutkan kedua array, lalu melangkahinya dengan hati-hati untuk mencari duplikat. Sesuatu seperti ini

fn overlapping(a: &Vec<i32>, b: &Vec<i32>) -> bool{
    let mut sa = a.clone();
    sa.sort();
    let mut sb = b.clone();
    sb.sort();
    let mut ai = 0;
    let mut bi = 0;
    while ai < a.len() && bi < b.len() {
        if sa[ai] < sb[bi] {
            ai += 1;
        } else if sa[ai] > sb[bi] {
            bi += 1;
        } else{
            return true;
        }
    }
    false
}

Tapi itu membutuhkan terlalu banyak mutasi untuk bisa bermain golf di Rust IMO :)

Python, 11 byte

set.__and__

Builtin yang membutuhkan 2 set dan melakukan persimpangan pada mereka

Aksioma, 50 221 byte

binSearch(x,v)==(l:=1;h:=#v;repeat(l>h=>break;m:=(l+h)quo 2;x<v.m=>(h:=m-1);x>v.m=>(l:=m+1);return m);0);g(a,b)==(if #a>#b then(v:=a;w:=b)else(v:=b;w:=a);c:=sort(v);for x in w repeat(if binSearch(x,c)~=0 then return 1);0)

ungolfed

--suppose v.1<=v.2<=....<=v.#v
--   binary serch of x in v, return the index i with v.i==x
--   return 0 if that index not exist
--traslated in Axiom from C  book
--Il Linguaggio C, II Edizione 
--Brian W.Kerninghan, Dennis M.Ritchie
binSearch(x,v)==
    l:=1;h:=#v  --1  4
    repeat
       l>h=>break
       m:=(l+h)quo 2   --m=(4+1)/2=5/2=2
                       --output [l,m,h]
       x<v.m=>(h:=m-1) --l x m  h =>  
       x>v.m=>(l:=m+1)
       return m
    0


g(a,b)==   
  if #a>#b then (v:=a;w:=b)
  else          (v:=b;w:=a)
  c:=sort(v)
  --output c
  for x in w repeat(if binSearch(x,c)~=0 then return 1)
  0

g (a, b) mendapatkan array yang lebih besar daripada win a dan b; misalkan memiliki elemen N: susunan array itu, lakukan pencarian biner dengan elemen array lainnya. Ini akan menjadi O (Nlog (N)). Ini mengembalikan 0 tanpa elemen a dalam b, 1 jika tidak.

hasil

(6) ->  g([1,2,3,4,-5], [5,7,6,8]), g([],[0]), g([],[]), g([1,2],[3,3]), g([3,2,1],[-4,3,5,6]), g([2,3],[2,2])
   Compiling function binSearch with type (PositiveInteger,List Integer
      ) -> NonNegativeInteger

   (6)  [0,0,0,0,1,1]
                                           Type: Tuple NonNegativeInteger

Jelly , 2 byte

œ&

Cobalah online!

Penjelasan

 œ&  Main link. Arguments: x y
⁸    (implicit) x
   ⁹ (implicit) y
 œ&  Intersection of x and y