Escreva um programa que terá como entrada 2 matrizes inteiras e retornará um valor verdadeiro se houver um elemento presente em ambas as matrizes ou, caso contrário, um falso. A solução óbvia para esse problema seria iterar cada elemento da primeira matriz e compará-lo com cada elemento da segunda, mas aqui está o problema: seu programa deve ter uma complexidade algorítmica de, no máximo, no pior caso, O ( NlogN), onde N é o comprimento da matriz mais longa,

Casos de teste:

 {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

Isso é código-golfe , então o código mais curto em bytes vence.

Na verdade , 1 byte

∩

Experimente online!

Esta é apenas a interseção definida incorporada. O valor resultante é a interseção dos dois conjuntos - uma lista não vazia (que é um valor verdadeiro) se houver uma interseção e uma lista vazia (que é um valor de falsey) caso contrário.

Complexidade

De acordo com o Python Wiki , a interseção de conjuntos tem uma complexidade temporal pior O(N*M)(de onde Ne Msão os comprimentos dos dois conjuntos). No entanto, a complexidade do tempo é tão ruim quando os dois conjuntos contêm objetos distintos, todos com o mesmo valor de hash (por exemplo {"some string"} & {hash("some string")}). Como os elementos do conjunto são apenas números inteiros nesse caso (e não há dois números inteiros com o mesmo valor, a menos que sejam iguais), a complexidade real do pior caso é O(min(N, M))(linear no comprimento do menor dos dois conjuntos). A construção de cada conjunto é O(N)(linear no número de elementos); portanto, a complexidade geral é O(max(N, M))(a complexidade é dominada pela construção do conjunto maior).

TSQL, 40 37 36 bytes

O SQL não possui matrizes, está usando tabelas

Retorna -1 para verdadeiro ou 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

Experimente

Ruby, 37 bytes:

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

Como na definição: "programa que terá como entrada 2 matrizes inteiras e retornará um valor verdadeiro se ...", este é um programa, aceita 2 matrizes como cadeias de caracteres na entrada, retorna verdadeiro ou falso.

como uma função - 14 bytes:

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

Complexidade:

A documentação ruby ​​do operador itnersection (&) diz "Ele compara elementos usando seus métodos hash e eql? Para eficiência.", O que suponho ser exatamente o que estamos procurando.

Empiricamente:

$ 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

O que parece confirmar isso.

Perl, 25 + 1 = 26 bytes em colaboração com o Dada

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

Corra com -a(penalidade de 1 byte).

Uma versão aprimorada do programa abaixo (que é mantida para ver o histórico da solução e mostrar a solução que eu encontrei por mim; também tem mais explicações). A -aopção lê matrizes separadas por espaço como entrada, armazenando-as @F. Usamos o %adicionário (acessado como $a{$_}) para armazenar uma máscara de bits em que as matrizes de entrada estão inseridas e imprimimos 1toda vez que vemos um elemento nas duas matrizes, ou seja, um valor maior que 2 dentro da máscara de bits resultante (felizmente, uma comparação falha retorna a cadeia nula, para printque não faça nada). Não podemos usar sayporque uma nova linha é verdadeira no Perl. O desempenho é assintoticamente o mesmo da versão mais antiga do programa (mas mais rápido em termos de fatores constantes).

Perl, 44 + 1 = 45 bytes

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

Corra com -p(penalidade de 1 byte). Insira uma matriz por linha, separando os elementos por espaços.

Isso funciona através da criação de uma tabela de hash %aque armazena uma máscara de bits das matrizes de entrada nas quais um valor foi visto. Se for visto na matriz na linha 1 e na linha 2, a máscara de bits armazenará o valor 3. hash e ver se 3 tem uma chave correspondente nos permite saber se existem valores em comum.

A complexidade desse algoritmo é O (n) se você considerar a criação de hash um tempo constante (ou seja, se você tiver números inteiros limitados, como o Perl). Se estiver usando números inteiros bignum (que podem ser inseridos neste programa, pois deixa a entrada como uma string), a complexidade do próprio algoritmo seria nominalmente O (n log n) para cada criação de hash e O (n) para o reversão de hash, que corresponde a O (n log n). No entanto, o algoritmo de hash do Perl sofre desempenho potencial de O (n²) com entrada selecionada com códigos maliciosos; o algoritmo é randomizado, no entanto, para tornar impossível determinar o que é essa entrada (e é possível que não possa ser acionada simplesmente com números inteiros), por isso é discutível com qual classe de complexidade ela "moralmente" conta. Felizmente, isso não importa no caso em que há '

Esse código funcionará para entradas que não sejam números inteiros, mas não funcionará para mais de duas matrizes (porque o código 3é codificado e porque a entrada na terceira linha não usaria máscaras corretamente, pois não é uma potência de 2). De maneira bastante irritante, o código naturalmente retorna um dos elementos duplicados, que é verdadeiro em quase todos os casos, mas "0"é falsey no Perl e um elemento duplicado válido na matriz. Como tal, tive que desperdiçar três bytes precedendo +a à saída, que é a maneira mais barata que encontrei para fornecer uma saída verdadeira no caso de borda das matrizes que se sobrepõem 0. Se eu estou autorizado a usar noções de truthy e Falsey de um idioma diferente do Perl (em que qualquer string não-vazia é truthy), você pode mudar "+$_"para $_salvar três bytes.

Python2 - 41 30 bytes

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

Interseção do conjunto: O (min (N, M)), onde N e M são o comprimento dos conjuntos.

Conversão de uma lista para um conjunto: O (max (N, M))

• Obrigado a Jakube por salvar 9 bytes! set(a).intersection(b)->set(a)&set(b)
• Obrigado ao Kade por economizar 2 bytes! -> removidof=

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)

isso converte a primeira lista em uma lista como [[i, 1], [i, 2] ...] a segunda lista em uma lista como [[1, i], [0, i] ...] onde i é a variável imaginária que mescla a lista 2 e faça um tipo que encontraria se houvesse um elemento da lista 1 na lista 2; portanto, é finalmente O (N log N) em que N = lista de comprimento 1 + lista de comprimento 2

destroçado

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

Eu não entendo por que ele "limpa" o código para re es ...

PowerShell, 88 78 77 23 bytes

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

Graças à @briantist para raspar um colossal 54 bytes do meu original, mais detalhado resposta pelo encurtamento -IncludeEqual, -ExcludeDifferente -Not!

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

Não consigo encontrar a fonte para Compare-Object( diffé um apelido para Compare-Object), então não tenho certeza da complexidade do tempo.

PHP , 15 bytes

array_intersect

Experimente online!

Um PHP embutido, como uma função que pode ser chamada / lambda. Retorno é um valor PHP truthy/ falseytestável. Além disso, de acordo com o outro envio do PHP, essa implementação deve atender aos requisitos de complexidade do desafio ( StackExchange ).

R, 23 bytes

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

Se assumirmos que sempre haverá um e apenas um elemento correspondente e que 1é um valor verdadeiro (que está em R ), então podemos escrever:

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

que é 21 bytes.

PHP, 55 51 bytes

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

Uso: salve em um arquivo e ligue do navegador:

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

intersect.php?a[]=1&a[]=2&a[]=3&b[]=0&b[]=4&b[]=1saídas 1para true.

Sobre a complexidade, não consegui encontrar referências, mas de acordo com a publicação deste StackOverflow, o script deve estar OK

GolfScript, 1 byte

Se aceitar a entrada diretamente como matrizes na pilha é permitido, esta solução GolfScript de um byte deve atender às especificações:

&

Se E / S baseada em texto for necessária, a entrada precisará ser avaliada primeiro, aumentando o comprimento em até dois bytes:

~&

Ambas as soluções usam o operador de interseção do array GolfScript, que é implementado usando o operador correspondente no Ruby . Eles retornam uma matriz vazia (que é falsa) se as matrizes não contiverem elementos correspondentes ou uma matriz não vazia (verdadeira) que contém todos os elementos correspondentes.

Até o momento, não consegui encontrar nenhuma documentação sobre a implementação interna ou a complexidade assintótica do operador de interseção do array Ruby, além da breve declaração de que "ele compara elementos usando seus métodos hash e eql? Para eficiência". No entanto, uma implementação razoável usando tabelas de hash seria executada em O ( n ) tempo (assumindo que hash e comparações são O (1)), e alguns testes rápidos de desempenho sugerem que esse é realmente o caso:

Esses testes foram realizados usando o programa GolfScript ~2?.2*,/&, que pega um número inteiro k , gera uma sequência aritmética de 2 × ^2k elementos, divide-o em duas matrizes de ^2k elementos e calcula sua interseção (obviamente vazia). As estrelas vermelhas mostram o tempo de execução medido t em segundos (em uma escala logarítmica) para vários valores de k , enquanto a linha verde representa a função t = c × 2 ^k , onde a constante de escala c ≈ 2 ^−17,075 foi escolhida da melhor maneira ajuste os dados medidos.

(Note-se que, em um gráfico log-log de como este, qualquer função polinomial da forma t = c × (2 ^k ) ^um produziria uma linha recta. No entanto, o declive da linha depende do expoente um , e os dados é certamente consistente com um = 1, como mostrado pela linha verde acima. Fwiw, o expoente de melhor ajuste numérica para este conjunto de dados foi um ≈ 1,00789).

JavaScript (ES6), 39 bytes

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

Será pior que O (n + m), mas espero que não seja tão ruim quanto O (n * m).

Ferrugem, 103 bytes

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

Pega duas fatias de matriz (ou referências a matrizes completas, elas desreferenciam as fatias automaticamente), agrupa-as em conjuntos e verifica a ausência de disjunção. Não tenho muita certeza de como a união de conjunto é implementada na biblioteca padrão do Rust, mas deve ser O (n + m) na pior das hipóteses.

Sem usar coleções, a alternativa mais fácil que eu vejo é classificar as duas matrizes e passar por cima delas com cuidado para procurar duplicatas. Algo assim

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
}

Mas isso exige muita mutação para ser divertido jogar golfe no Rust IMO :)

Python, 11 bytes

set.__and__

Builtin que leva 2 conjuntos e faz uma interseção neles

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)

destroçado

--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) obtém a matriz maior entre be awin; suponha que ele tenha N elementos: classifique essa matriz, faça uma pesquisa binária com elementos dessa outra matriz. Isso seria O (Nlog (N)). Retorna 0 para nenhum elemento de a em b, 1 caso contrário.

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

Geléia , 2 bytes

œ&

Experimente online!

Explicação

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