Escriba un programa que tome como entrada 2 matrices enteras y devuelva un valor verdadero si existe un elemento que esté presente en ambas matrices, o uno falso de lo contrario. La solución obvia a este problema sería iterar a través de cada elemento en el primer conjunto y compararlo con cada elemento en el segundo, pero aquí está el truco: su programa debe tener una complejidad algorítmica como máximo, en el peor de los casos, O ( NlogN), donde N es la longitud de la matriz más larga,

Casos de prueba:

 {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

Este es el código de golf , por lo que gana el código más corto en bytes.

En realidad , 1 byte

∩

Pruébalo en línea!

Esto es simplemente la intersección establecida incorporada. El valor resultante es la intersección de los dos conjuntos: una lista no vacía (que es un valor verdadero) si hay una intersección, y una lista vacía (que es un valor falso) de lo contrario.

Complejidad

De acuerdo con Python Wiki , la intersección de conjuntos tiene una complejidad de tiempo en el peor de los casos O(N*M)(dónde Ny Mson las longitudes de los dos conjuntos). Sin embargo, la complejidad del tiempo es tan mala cuando los dos conjuntos contienen objetos distintos que tienen el mismo valor hash (por ejemplo {"some string"} & {hash("some string")}). Dado que los elementos del conjunto son solo enteros en este caso (y no hay dos enteros hash al mismo valor a menos que sean iguales), la complejidad real del peor de los casos es O(min(N, M))(lineal en la longitud del menor de los dos conjuntos). La construcción de cada conjunto es O(N)(lineal en el número de elementos), por lo que la complejidad general es O(max(N, M))(la complejidad está dominada por la construcción del conjunto más grande).

TSQL, 40 37 36 bytes

SQL no tiene matrices, en su lugar utiliza tablas

Devuelve -1 para verdadero o 0 para falso

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

Pruébalo

Ruby, 37 bytes:

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

Como en la definición: "programa que tomará como entrada 2 matrices enteras y devolverá un valor verdadero si ...", este es un programa, acepta 2 matrices como cadenas en la entrada, devuelve verdadero o falso.

como una función - 14 bytes:

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

Complejidad:

La documentación de ruby ​​del operador itnersection (&) dice "Compara elementos usando sus métodos hash y eql? Para eficiencia", lo que supongo que es exactamente lo que estamos buscando.

Empíricamente:

$ 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

Lo que parece confirmarlo.

Perl, 25 + 1 = 26 bytes en colaboración con Dada

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

Ejecutar con -a(1 byte de penalización).

Una versión mejorada del programa a continuación (que se mantiene para ver el historial de la solución y para mostrar la solución que encontré yo mismo; también tiene más explicaciones). La -aopción lee las matrices separadas por espacios como la entrada y las almacena @F. Usamos el %adiccionario (al que se accede como $a{$_}) para almacenar una máscara de bits de las matrices de entrada en las que se encuentra la entrada, e imprimimos 1cada vez que vemos un elemento en ambas matrices, es decir, un valor superior a 2 dentro de la máscara de bits resultante (afortunadamente, una comparación fallida devuelve la cadena nula, por lo printque no hace nada). No podemos usar sayporque una nueva línea es verdadera en Perl. El rendimiento es asintóticamente igual que la versión anterior del programa (pero más rápido en términos de factores constantes).

Perl, 44 + 1 = 45 bytes

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

Ejecutar con -p(1 byte de penalización). Ingrese una matriz por línea, separando los elementos por espacios.

Esto funciona mediante la creación de una tabla hash %aque almacena una máscara de bits de las matrices de entrada en las que se ha visto un valor. Si se ha visto tanto en la matriz en la línea 1 como en la línea 2, la máscara de bits almacenará el valor 3. Invertir el hash y ver si 3 tiene una clave correspondiente nos permite saber si hay valores en común.

La complejidad de este algoritmo es O (n) si considera que la creación de hash es un tiempo constante (es decir, si tiene enteros acotados, como lo hace Perl). Si se usan enteros bignum (que podrían ingresarse en este programa, ya que dejan la entrada como una cadena), la complejidad del algoritmo en sí sería nominalmente O (n log n) para cada creación de hash, y O (n) para inversión de hash, que se suma a O (n log n). Sin embargo, el algoritmo de hash de Perl adolece de un rendimiento potencial de O (n²) con entrada seleccionada de forma maliciosa; Sin embargo, el algoritmo es aleatorio, para que sea imposible determinar cuál es esa entrada (y es posible que no pueda activarse simplemente con enteros), por lo que es discutible con qué clase de complejidad cuenta "moralmente". Afortunadamente, esto no importa en el caso de que haya

Este código funcionará para entradas que no sean enteros, pero no funcionará para más de dos matrices (porque 3está codificado y porque la entrada en la tercera línea no enmascararía correctamente, ya que no es una potencia de 2). Bastante molesto, el código devuelve naturalmente uno de los elementos duplicados, lo cual es cierto en casi todos los casos, pero "0"es falso en Perl y un elemento duplicado válido en la matriz. Como tal, tuve que desperdiciar tres bytes anteponiendo a +a la salida, que es la forma más barata que encontré para dar una salida verdadera en el caso de borde de las matrices superpuestas 0. Si se me permite usar nociones de veracidad y falsedad de un lenguaje que no sea Perl (en el que cualquier cadena no vacía es veraz), puede cambiar "+$_"a $_para guardar tres bytes.

Python2 - 41 30 bytes

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

Intersección de conjuntos: O (min (N, M)) donde N y M son la longitud de los conjuntos.

Conversión de una lista a un conjunto: O (max (N, M))

• ¡Gracias a Jakube por guardar 9 bytes! set(a).intersection(b)->set(a)&set(b)
• ¡Gracias a Kade por guardar 2 bytes! -> eliminadof=

Axioma, 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)

esto convierte la primera lista en una lista como [[i, 1], [i, 2] ...] la segunda lista en una lista como [[1, i], [0, i] ...] donde i es la variable imaginaria que fusiona la lista 2, y hace un tipo que encontraría si hay un elemento de la lista 1 en la lista 2, por lo que es al final O (N log N) donde N = longitud lista 1 + longitud lista 2

sin golf

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

resultados

(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

no entiendo por qué "borra" el código para r y s ...

PowerShell, 88 78 77 23 bytes

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

Gracias a @briantist para el afeitado de la friolera de 54 bytes de mi original, más prolija respuesta acortando -IncludeEqual, -ExcludeDifferenty -Not!

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

No puedo encontrar la fuente de Compare-Object( diffes un alias para Compare-Object), por lo que no estoy seguro de la complejidad del tiempo.

PHP , 15 bytes

array_intersect

Pruébalo en línea!

Un PHP incorporado, como una función invocable / lambda. El retorno es un valor PHP truthy/ falseycomprobable. Además, según el otro envío de PHP, esta implementación debe cumplir con los requisitos de complejidad del desafío ( StackExchange ).

R, 23 bytes

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

Si suponemos que siempre habrá una coincidencia de un solo elemento y que ese 1es un valor verdadero (que está en R ), entonces podemos escribir:

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

que es de 21 bytes.

PHP, 55 51 bytes

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

Uso: guardar en un archivo y llamar desde el navegador:

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

intersect.php?a[]=1&a[]=2&a[]=3&b[]=0&b[]=4&b[]=1salidas 1paratrue.

Sobre la complejidad, no pude encontrar referencias, pero de acuerdo con esta publicación de StackOverflow, el script debería estar bien

GolfScript, 1 byte

Si se permite tomar la entrada directamente como matrices en la pila, esta solución GolfScript de un byte debe cumplir con las especificaciones:

&

Si se requiere E / S basada en texto, primero se debe evaluar la entrada, empujando la longitud hasta dos bytes:

~&

Ambas soluciones utilizan el operador de intersección de matriz GolfScript, que se implementa utilizando el operador correspondiente en Ruby . Devuelven una matriz vacía (que es falsa) si las matrices no contienen elementos coincidentes, o una matriz no vacía (que es verdad) que contiene todos los elementos coincidentes de lo contrario.

Hasta ahora no he podido encontrar ninguna documentación sobre la implementación interna o la complejidad asintótica del operador de intersección de la matriz de Ruby, más allá de la breve afirmación de que "compara elementos usando sus métodos hash y eql? Para mayor eficiencia". Sin embargo, una implementación razonable utilizando tablas hash se ejecutaría en tiempo O ( n ) (suponiendo que el hashing y las comparaciones sean O (1)), y algunas pruebas de rendimiento rápidas sugieren que este es el caso:

Estas pruebas se llevaron a cabo utilizando el programa GolfScript ~2?.2*,/&, que toma un número entero k , genera una secuencia aritmética de 2 × 2 ^k elementos, la divide en dos conjuntos de 2 ^k elementos y calcula su intersección (obviamente vacía). Las estrellas rojas muestran el tiempo de ejecución medido t en segundos (en una escala logarítmica) para varios valores de k , mientras que la línea verde representa la función t = c × 2 ^k , donde la constante de escala c ≈ 2 ^−17.075 se eligió mejor ajusta los datos medidos.

(Tenga en cuenta que, en un diagrama log-log como este, cualquier función polinómica de la forma t = c × (2 ^k ) ^a produciría una línea recta. Sin embargo, la pendiente de la línea depende del exponente a , y los datos es ciertamente consistente con a = 1 como se muestra en la línea verde de arriba. FWIW, el exponente numérico de mejor ajuste para este conjunto de datos fue un ≈ 1.00789.)

JavaScript (ES6), 39 bytes

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

Será peor que O (n + m) pero con suerte no tan malo como O (n * m).

Óxido, 103 bytes

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

Toma dos rebanadas de matriz (o referencias a matrices completas, desreferencian a las rebanadas automáticamente), las agrupa en conjuntos y verifica la no disyunción. No estoy muy seguro de cómo se implementa set union en la biblioteca estándar Rust, pero debería ser O (n + m) en el peor de los casos.

Sin usar colecciones, la alternativa más fácil que veo es ordenar ambas matrices, luego pasarlas cuidadosamente para buscar duplicados. Algo como esto

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
}

Pero eso requiere demasiada mutación para ser divertido al golf en Rust IMO :)

Python, 11 bytes

set.__and__

Construido que toma 2 series y hace una intersección en ellas

Axioma, 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)

sin golf

--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) obtiene la matriz más grande beetwin ayb; supongamos que tiene N elementos: clasifique esa matriz, haga una búsqueda binaria con elementos que otra matriz. Esto sería O (Nlog (N)). Devuelve 0 para ningún elemento de a en b, 1 de lo contrario.

resultados

(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

Jalea , 2 bytes

œ&

Pruébalo en línea!

Explicación

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