Schreiben Sie ein Programm, das für die Eingabe von 2 ganzzahligen Arrays verwendet und einen wahrheitsgemäßen Wert zurückgibt, wenn ein Element vorhanden ist, das in beiden Arrays vorhanden ist, oder ein falsches Element auf andere Weise. Die offensichtliche Lösung für dieses Problem wäre, jedes Element im ersten Array zu durchlaufen und es mit jedem Element im zweiten zu vergleichen. Hier ist jedoch der Haken: Ihr Programm muss eine algorithmische Komplexität von höchstens O (im schlimmsten Fall) aufweisen. NlogN), wobei N die Länge des längeren Arrays ist,

Testfälle:

 {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

Dies ist Code-Golf , also gewinnt der kürzeste Code in Bytes.

Eigentlich 1 Byte

∩

Probieren Sie es online aus!

Dies ist lediglich die eingebaute festgelegte Kreuzung. Der resultierende Wert ist der Schnittpunkt der beiden Mengen - eine nicht leere Liste (die ein wahrheitsgemäßer Wert ist), wenn es einen Schnittpunkt gibt, und eine leere Liste (die ein falscher Wert ist), andernfalls.

Komplexität

Laut dem Python-Wiki hat die Mengenschnittstelle eine Zeitkomplexität im ungünstigsten Fall von O(N*M)(wobei Nund Msind die Längen der beiden Mengen). Die zeitliche Komplexität ist jedoch nur dann so schlecht, wenn die beiden Sätze unterschiedliche Objekte enthalten, die alle denselben Hashwert haben (z. B. {"some string"} & {hash("some string")}). Da die Mengenelemente in diesem Fall nur Ganzzahlen sind (und keine zwei Ganzzahlen den gleichen Wert haben, es sei denn, sie sind gleich), ist die tatsächliche Komplexität im ungünstigsten Fall O(min(N, M))(linear in der Länge der kleineren der beiden Mengen). Die Konstruktion jeder Menge ist O(N)(linear in der Anzahl der Elemente), also ist die Gesamtkomplexität O(max(N, M))(die Komplexität wird durch die Konstruktion der größeren Menge dominiert).

TSQL, 40 37 36 Bytes

SQL hat keine Arrays, sondern verwendet stattdessen Tabellen

Gibt -1 für wahr oder 0 für falsch zurück

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

Versuch es

Ruby, 37 Bytes:

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

Wie in der Definition: "Programm, das für die Eingabe 2 ganzzahlige Arrays verwendet und einen wahrheitsgemäßen Wert zurückgibt, wenn ...", ist dies ein Programm, das 2 Arrays als Zeichenfolgen in der Eingabe akzeptiert, true oder false zurückgibt.

als Funktion - 14 Bytes:

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

Komplexität:

In der Ruby-Dokumentation des Operators itnersection (&) heißt es: "Es vergleicht Elemente mit ihren Hash- und EQL-Methoden, um die Effizienz zu steigern." Ich nehme an, genau das ist, wonach wir suchen.

Empirisch:

$ 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

Welches scheint es zu bestätigen.

Perl, 25 + 1 = 26 Bytes in Zusammenarbeit mit Dada

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

Führen Sie mit -a(1 Byte Strafe).

Eine verbesserte Version des folgenden Programms (die aufbewahrt wird, um den Verlauf der Lösung anzuzeigen und die Lösung zu zeigen, die ich selbst gefunden habe; sie enthält auch weitere Erklärungen). Die -aOption liest durch Leerzeichen getrennte Arrays als Eingabe und speichert sie in @F. Wir verwenden das %aWörterbuch (Zugriff als $a{$_}), um eine Bitmaske zu speichern, in der sich die Eingabearrays befinden, und drucken 1jedes Mal, wenn in beiden Arrays ein Element angezeigt wird, dh ein Wert über 2 in der resultierenden Bitmaske (glücklicherweise wird ein fehlgeschlagener Vergleich zurückgegeben die Nullzeichenfolge, also printmacht die nichts). Wir können nicht verwenden, sayweil eine Newline in Perl wahr ist. Die Leistung ist asymptotisch dieselbe wie bei der älteren Version des Programms (jedoch schneller in Bezug auf konstante Faktoren).

Perl, 44 + 1 = 45 Bytes

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

Führen Sie mit -p(1 Byte Strafe). Geben Sie ein Array pro Zeile ein und trennen Sie die Elemente durch Leerzeichen.

Dies funktioniert durch Erstellen einer Hash-Tabelle %a, in der eine Bitmaske der Eingabearrays gespeichert wird, in denen ein Wert angezeigt wurde. Wenn dies sowohl im Array in Zeile 1 als auch in Zeile 2 angezeigt wird, speichert die Bitmaske daher den Wert 3. Umkehren der Wenn Sie sehen, ob 3 einen entsprechenden Schlüssel hat, wissen Sie, ob es gemeinsame Werte gibt.

Die Komplexität dieses Algorithmus ist O (n), wenn Sie die Hash-Erstellung als konstante Zeit betrachten (wenn Sie ganze Zahlen begrenzt haben, wie es Perl tut). Bei Verwendung von Bignum-Ganzzahlen (die in dieses Programm eingegeben werden könnten, da die Eingabe als Zeichenfolge belassen wird) wäre die Komplexität des Algorithmus selbst nominell O (n log n) für jede Hash-Erstellung und O (n) für die Hash-Umkehrung, die sich zu O (n log n) addiert. Der Hashing-Algorithmus von Perl leidet jedoch unter der potenziellen O (n²) -Leistung bei böswillig ausgewählten Eingaben. Der Algorithmus ist jedoch randomisiert, um es unmöglich zu machen, zu bestimmen, was diese Eingabe ist (und es ist möglich, dass sie nicht einfach mit ganzen Zahlen ausgelöst werden kann). Daher ist es fraglich, mit welcher Komplexitätsklasse sie "moralisch" zählt. Zum Glück spielt dies keine Rolle, wenn es dort ist. '

Dieser Code funktioniert für andere Eingaben als Ganzzahlen, aber nicht für mehr als zwei Arrays (weil der fest 3codiert ist und weil die Eingabe in der dritten Zeile die Bitmaske nicht korrekt ist, da es sich nicht um eine Zweierpotenz handelt). Eher ärgerlich ist, dass der Code natürlich eines der doppelten Elemente zurückgibt, was in fast allen Fällen "0"wahr ist, in Perl jedoch falsch ist und ein gültiges doppeltes Element im Array darstellt. Als solches musste ich drei Bytes vor +der Ausgabe verschwenden , was der billigste Weg ist, eine wahrheitsgemäße Ausgabe im Randfall der Arrays zu liefern, die sich bei überlappen 0. Wenn ich darf Vorstellungen von truthy und Falsey aus einer anderen Sprache als Perl (in dem jede nicht leere Zeichenkette ist truthy) verwenden, können Sie ändern , "+$_"um $_drei Byte zu speichern.

Python2 - 41 30 Bytes

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

Mengenschnittpunkt: O (min (N, M)) wobei N und M die Länge der Mengen sind.

Konvertierung von einer Liste in eine Menge: O (max (N, M))

• Vielen Dank an Jakube für das Speichern von 9 Bytes! set(a).intersection(b)->set(a)&set(b)
• Vielen Dank an Kade für das Speichern von 2 Bytes! -> entferntf=

Axiom, 439 Bytes

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)

Dies konvertiert die erste Liste in einer Liste als [[i, 1], [i, 2] ...] die zweite Liste in einer Liste als [[1, i], [0, i] ...] wobei i ist die imaginäre Variable, die die Liste 2 zusammenführt und eine Sortierung vornimmt, die ermittelt, ob ein Element der Liste 1 in der Liste 2 vorhanden ist, sodass es endlich O (N log N) ist, wobei N = Länge Liste 1 + Länge Liste 2 ist

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

Ergebnisse

(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

Ich verstehe nicht, warum es Code für r und s "löscht" ...

PowerShell, 88 78 77 23 Byte

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

Dank @briantist für Abschaben eines satten 54 Bytes von meinem ursprünglichen, ausführlichere Antwort durch Verkürzung -IncludeEqual, -ExcludeDifferentund -Not!

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

Ich kann die Quelle für nicht finden Compare-Object( diffist ein Alias ​​für Compare-Object), daher bin ich mir der zeitlichen Komplexität nicht sicher.

PHP , 15 Bytes

array_intersect

Probieren Sie es online aus!

Ein integriertes PHP als aufrufbare / Lambda-Funktion. Return ist ein PHP truthy/ falseytestbarer Wert. Gemäß der anderen PHP-Übermittlung sollte diese Implementierung auch die Anforderungen an die Komplexität der Herausforderung ( StackExchange ) erfüllen .

R, 23 Bytes

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

Wenn wir davon ausgehen, dass immer nur ein Element übereinstimmt und dies 1ein wahrer Wert ist (der in R angegeben ist ), können wir schreiben:

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

Das sind 21 Bytes.

PHP, 55 51 Bytes

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

Verwendung: In einer Datei speichern und vom Browser aus aufrufen:

intersect.php?a[]=1&a[]=2&a[]=3&b[]=0&b[]=4&b[]=5Ausgänge 0für false.

intersect.php?a[]=1&a[]=2&a[]=3&b[]=0&b[]=4&b[]=1Ausgänge 1für true.

In Bezug auf die Komplexität konnte ich keine Referenzen finden, aber laut diesem Beitrag von StackOverflow sollte das Skript in Ordnung sein

GolfScript, 1 Byte

Wenn die Eingabe direkt als Arrays auf dem Stapel zulässig ist, sollte diese Ein-Byte-GolfScript-Lösung die folgenden Spezifikationen erfüllen:

&

Wenn textbasierte E / A erforderlich ist, muss die Eingabe zuerst ausgewertet werden, wobei die Länge auf zwei Bytes erhöht wird:

~&

Beide Lösungen verwenden den GolfScript-Array-Schnittpunktoperator, der mit dem entsprechenden Operator in Ruby implementiert wird . Sie geben ein leeres Array (das falsch ist) zurück, wenn die Arrays keine übereinstimmenden Elemente enthalten, oder ein nicht leeres Array (das wahr ist), das ansonsten alle übereinstimmenden Elemente enthält.

Ich konnte bisher keine Dokumentation über die interne Implementierung oder die asymptotische Komplexität des Ruby-Array-Schnittpunktoperators finden, abgesehen von der kurzen Aussage, dass "Elemente mit ihren Hash- und EQL-Methoden auf Effizienz verglichen werden". Eine vernünftige Implementierung unter Verwendung von Hash-Tabellen würde jedoch in O ( n ) -Zeit ausgeführt (vorausgesetzt, Hashing und Vergleiche sind O (1)), und einige schnelle Leistungstests legen nahe, dass dies tatsächlich der Fall ist:

Diese Tests wurden mit dem GolfScript-Programm durchgeführt ~2?.2*,/&, das eine ganze Zahl k verwendet , eine arithmetische Folge von 2 × 2 ^k Elementen erzeugt, diese in zwei Arrays von 2 ^k Elementen aufteilt und ihren (offensichtlich leeren) Schnittpunkt berechnet. Die roten Sterne zeigen die gemessene Ausführungszeit t in Sekunden (auf einer logarithmischen Skala) für verschiedene Werte von k , während die grüne Linie die Funktion t = c × 2 ^{k darstellt} , wobei die Skalierungskonstante c ≈ 2 ^−17.075 am besten gewählt wurde Passen Sie die gemessenen Daten an.

(Beachten Sie, dass in einem Log-Log-Diagramm wie diesem jede Polynomfunktion der Form t = c × (2 ^k ) ^a eine gerade Linie ergeben würde. Die Steigung der Linie hängt jedoch vom Exponenten a und den Daten ab ist mit Sicherheit bei gleichbleibenden einem = 1 wie oben. FWIW durch die grüne Linie dargestellt ist , die numerischen best-fit - Exponenten für diesen Datensatz war ein ≈ 1,00789) .

JavaScript (ES6), 39 Byte

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

Wird schlechter als O (n + m) sein, aber hoffentlich nicht so schlecht wie O (n * m).

Rost, 103 Bytes

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

Nimmt zwei Array-Slices (oder Verweise auf vollständige Arrays, sie werden automatisch auf Slices dereferenziert), bündelt sie zu Sets und prüft, ob sie nicht disjunkt sind. Ich bin nicht ganz sicher, wie Set Union in der Rust-Standardbibliothek implementiert ist, aber es sollte im schlimmsten Fall O (n + m) sein.

Ohne Sammlungen zu verwenden, besteht die einfachste Alternative darin, beide Arrays zu sortieren und sie dann sorgfältig zu durchsuchen, um nach Duplikaten zu suchen. Etwas wie das

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
}

Aber das erfordert zu viel Mutation, um Spaß beim Golfen in Rust IMO zu haben :)

Python, 11 Bytes

set.__and__

Eingebaut, das 2 Sätze nimmt und eine Kreuzung auf ihnen macht

Axiom, 50 221 Bytes

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) erhält das größere Array zwischen a und b; Angenommen, es hat N Elemente: Sortieren Sie das Array, führen Sie eine binäre Suche mit Elementen des anderen Arrays durch. Dies wäre O (Nlog (N)). Es gibt 0 für kein Element von a in b, andernfalls 1 zurück.

Ergebnisse

(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

Gelee , 2 Bytes

œ&

Probieren Sie es online aus!

Erläuterung

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