Dada uma matriz a que contém apenas números no intervalo de 1 a a.length, encontre o primeiro número duplicado para o qual a segunda ocorrência possui o índice mínimo. Em outras palavras, se houver mais de 1 número duplicado, retorne o número para o qual a segunda ocorrência possui um índice menor que a segunda ocorrência do outro número. Se não houver tais elementos, seu programa / função poderá resultar em um comportamento indefinido.

Exemplo:

Pois a = [2, 3, 3, 1, 5, 2], a saída deve ser firstDuplicate(a) = 3.

Existem 2 duplicatas: números 2 e 3. A segunda ocorrência de 3 tem um índice menor que a segunda ocorrência de 2, portanto a resposta é 3.

Pois a = [2, 4, 3, 5, 1], a saída deve ser firstDuplicate(a) = -1.

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

BÔNUS: Você pode resolvê-lo em O (n) complexidade de tempo e O (1) complexidade adicional de espaço?

Python 2 , 34 bytes

O (n ² ) tempo, O (n) espaço

^{Economizou 3 bytes graças a @vaultah e mais 3 de @xnor!}

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

Experimente online!

JavaScript (ES6), 47 36 31 25 bytes

Economizou 6 bytes graças a ThePirateBay

Retorna undefinedse não houver solução.

Complexidade do tempo: O (n) :-)
Complexidade do espaço: O (n) :-(

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

Quão?

Nós manter o controle de valores já encontradas por salvá-los como novas propriedades da matriz original um usando números negativos. Dessa forma, eles não podem interferir nas entradas originais.

Demo

let f =

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

console.log(f([2, 3, 3, 1, 5, 2]))
console.log(f([2, 4, 3, 5, 1]))
console.log(f([1, 2, 3, 4, 1]))

Mathematica, 24 bytes

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

A capacidade de correspondência de padrões do Mathematica é muito legal!

Retorna o original Listpara entrada inválida.

Explicação

#/.

Na entrada, substitua ...

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

A Listcom um elemento duplicado, com 0 ou mais elementos antes, entre e depois das duplicatas ...

... :>a

Com o elemento duplicado.

Geléia , 5 bytes

Ṛœ-QṪ

Experimente online!

Como funciona

Ṛœ-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.

Haskell , 35 bytes

f s(h:t)|h`elem`s=h|1<2=f(h:s)t
f[]

Experimente online! Falha se nenhuma duplicata for encontrada.

Gelatina , 6 bytes

xŒQ¬$Ḣ

Experimente online!

Retorna a primeira duplicata ou 0 se não houver duplicata.

Explicação

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

Japonês , 7 bytes

æ@bX ¦Y

Teste online!

Explicação

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

Alternativamente:

æ@¯Y øX

Teste online!

Explicação

 æ@   ¯ 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

Pitão, 5 bytes

h.-Q{

Suíte de teste

Remova de Q a primeira aparência de cada elemento em Q e, em seguida, retorne o primeiro elemento.

Dyalog APL, 27 24 20 19 13 12 11 bytes

⊢⊃⍨0⍳⍨⊢=⍴↑∪

Agora modificado para não depender da v16! Experimente online!

Quão? (Com entrada N )

• ⊢⊃⍨...- N neste índice:
  • ⍴↑∪- N com duplicatas removidas, acolchoado à direita com o 0tamanho N
  • ⊢=- Igualdade entre elementos com N
  • 0⍳⍨- Índice do primeiro 0. `

Python 3 , 94 92 bytes

O (n) tempo e O (1) memória extra.

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

Experimente online!

Fonte do algoritmo .

Explicação

A idéia básica do algoritmo é percorrer cada elemento da esquerda para a direita, acompanhar os números que apareceram e retornar o número ao atingir um número que já apareceu e retornar -1 depois de percorrer cada elemento.

No entanto, ele usa uma maneira inteligente de armazenar os números que apareceram sem o uso de memória extra: para armazená-los como o sinal do elemento indexado pelo número. Por exemplo, eu posso representar o fato de que 2e 3já apareceu por ter a[2]e a[3]negativo, se a matriz estiver indexada em 1.

Perl 6 , 13 bytes

*.repeated[0]

Tente

Explicação

• A posição *está em um termo, portanto, toda a instrução é uma lambda WhateverCode .

• O .repeatedé um método que resulta em todos os valores, exceto pela primeira vez que cada valor foi visto.

  say [2, 3, 3, 3, 1, 5, 2, 3].repeated.perl; # (3, 3, 2, 3).Seq
  #   (      3, 3,       2, 3).Seq

• [0]apenas retorna o primeiro valor na Seq .
  Se não houver valor, nada será retornado.
  ( Nil é a base dos tipos de falha e todos os tipos têm seu próprio valor indefinido, portanto, nulo é diferente de um valor indefinido na maioria dos outros idiomas)

Observe que, como a implementação de.repeated gera uma Seq, isso significa que ela não começa a fazer nenhum trabalho até que você solicite um valor, e apenas faz o suficiente para gerar o que você solicita.
Portanto, seria fácil argumentar que isso tem, na pior das hipóteses, O (n)  complexidade de tempo e, na melhor das hipóteses, O (2)  complexidade de tempo se o segundo valor for uma repetição do primeiro.
Provavelmente semelhante pode ser dito sobre a complexidade da memória.

APL (Dyalog) , 20 bytes

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

Experimente online!

2⍴¯1 um negativo r eshaped em uma lista de comprimento dois

⎕, obter entrada (mnemonic: console box) e preceder a essa

n← armazenar isso em n

,\ prefixos de n (lit. concatenação cumulativa)

(… )¨ Aplique a seguinte função tácita a cada prefixo

 , [é] a viagem (apenas garante que o prefixo seja uma lista)

 ≢ diferente de

 ∪ os elementos únicos [?] (ou seja, o prefixo tem duplicatas?)

n/⍨ use isso para filtrar n (remove todos os elementos até o primeiro para o qual uma duplicata foi encontrada)

⊃ escolha o primeiro elemento desse

APL (Dyalog) , 11 bytes

De acordo com as novas regras , gera um erro se não houver duplicatas.

⊢⊃⍨⍬⍴⍳∘≢~⍳⍨

Experimente online!

⍳⍨ os índices da primeira ocorrência de cada elemento

~ removido de

⍳∘≢ de todos os índices

⍬⍴ remodelar isso em um escalar (dá zero se nenhum dado estiver disponível)

⊃⍨ use isso para escolher (dá erro zero)

⊢ o argumento

APL, 15

{⊃⍵[(⍳⍴⍵)~⍵⍳⍵]}

Parece que podemos retornar 0 em vez de -1 quando não houver duplicatas (obrigado Adám pelo comentário). Então, 3 bytes a menos.

Um pouco de descrição:

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

Para referência, a solução antiga adicionou -1 à lista no final; portanto, se a lista acabar vazia, ela conteria -1 e o primeiro elemento seria -1.

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

Experimente em tryapl.org

Retina , 26 24 bytes

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

Experimente online! Explicação: \b(\d+)\bcorresponde a cada número por vez e, a seguir, olha para trás para ver se o número é uma duplicata; se for a primeira 1partida, é !emitido, em vez da contagem de partidas. Infelizmente, colocar o lookbehind em primeiro lugar não parece funcionar, caso contrário, ele salvaria vários bytes. Edit: Adicionado 7 bytes para cumprir com o -1valor de retorno em nenhuma correspondência. Economizou 2 bytes graças a @MartinEnder.

MATL , 8 bytes

&=Rsqf1)

Dá um erro (sem saída) se não existir duplicado.

Experimente o MATL Online!

Explicação

&=   % 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

R, 34 bytes

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

Corte alguns caracteres da resposta de @djhurio, mas não tenha reputação suficiente para comentar.

J, 17 16 bytes

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

Quão?

(*/{_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

R , 28 bytes

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

Experimente online!

J , 12 bytes

,&_1{~~:i.0:

Experimente online!

Explicação

,&_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

Dyalog APL Classic, 18 caracteres

Só funciona em ⎕IO←0.

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

Remova da lista de índices dos elementos do argumento com um "-1" anexado os índices da lista de seu nub e, em seguida, escolha o primeiro que resta. Se após a remoção restar apenas um vetor vazio, seu primeiro elemento será por definição 0, que é usado para indexar o argumento estendido produzindo o -1 desejado.

Ruby , 28 36 bytes

Mal entendeu o desafio pela primeira vez. O(n)tempo, O(n)espaço.

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

Experimente online!

Java (OpenJDK 8) , 65 117 109 bytes

Solução anterior de 65 bytes:

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

Nova solução. 19 bytes são incluídos paraimport java.math.*;

-8 bytes graças a @Nevay

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

Experimente online!

Editar

O algoritmo no meu programa original estava bom, mas o tamanho estático do tipo de dados usado significava que ele quebrou rapidamente quando o tamanho ficou acima de um certo limite.

Alterei o tipo de dados usado no cálculo para aumentar o limite de memória do programa para acomodar isso (usando BigIntegerprecisão arbitrária em vez de intou long). No entanto, isso torna discutível se isso conta ou não como O(1)complexidade de espaço.

Deixarei intacta minha explicação abaixo, mas desejo acrescentar que agora acredito que é impossível alcançar a O(1)complexidade do espaço sem fazer algumas suposições.

Prova

Defina Ncomo um número inteiro tal que 2 <= N.

Let SSer uma lista representando uma série de números inteiros aleatórios [x{1}, ..., x{N}], onde x{i}tem a restrição 1 <= x{i} <= N.

A complexidade do tempo (na notação Big-O) necessária para percorrer esta lista exatamente uma vez por elemento é O(n)

O desafio dado é encontrar o primeiro valor duplicado na lista. Mais especificamente, estamos pesquisando o primeiro valor em Sque é uma duplicata de um item anterior na lista.

Seja pe qseja a posição de dois elementos na lista, tais que p < qe x{p} == x{q}. Nosso desafio passa a ser encontrar o menor qque satisfaça essas condições.

A abordagem óbvia para esse problema é iterar através de S e verificar se x{i}existe em outra lista T: se x{i}não existir T, armazenamos T. Se x{i}existe T, é o primeiro valor duplicado e, portanto, o menor q, e, como tal, o retornamos. Essa eficiência de espaço é O(n).

Para alcançar a O(1)complexidade do espaço e, ao mesmo O(n)tempo, manter a complexidade do tempo, precisamos armazenar informações exclusivas sobre cada objeto da lista em uma quantidade finita de espaço. Por esse motivo, a única maneira de qualquer algoritmo executar emO(1)a complexidade do espaço é se: 1. N recebe um limite superior correspondente à memória necessária para armazenar o número máximo de valores possíveis para um tipo de dados finito específico. 2. A reatribuição de uma única variável imutável não é contada de acordo com a complexidade, apenas o número de variáveis ​​(uma lista sendo várias variáveis). 3. (Com base em outras respostas) A lista é (ou pelo menos os elementos da lista são) mutáveis ​​e o tipo de dados da lista é predefinido como um número inteiro assinado, permitindo que alterações sejam feitas nos elementos adicionais da lista sem usar memória adicional.

1 e 3 exigem suposições e especificações sobre o tipo de dados, enquanto 2 exige que apenas o número de variáveis ​​seja considerado para o cálculo da complexidade do espaço, em vez do tamanho dessas variáveis. Se nenhuma dessas suposições for aceita, seria impossível obter O(n)complexidade de tempo e O(1)complexidade de espaço.

Explicação

Uau, rapaz, este levou um tempo embaraçosamente longo para pensar um pouco no poder do cérebro.

Então, pegar o bônus é difícil. Precisamos operar sobre a lista inteira exatamente uma vez e rastrear quais valores já foram repetidos sem complexidade adicional de espaço.

A manipulação de bits resolve esses problemas. Inicializamos nosso O(1)'armazenamento', um par de números inteiros, depois percorremos a lista, OU inserindo o i-ésimo bit em nosso primeiro número inteiro e armazenando o resultado no segundo.

Por exemplo, se temos 1101e realizamos uma operação OR 10, obtemos 1111. Se fizermos outra sala de cirurgia 10, ainda temos 1101.

Logo, quando realizamos a operação OR e terminamos com o mesmo número, encontramos nossa duplicata. Nenhuma duplicata na matriz faz com que o programa atropele e lance uma exceção.

PHP, 56 44 38 32 bytes

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

Execute assim:

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

Explicação

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

• 12 bytes salvos usando variáveis ​​em vez de uma matriz
• Economizou 6 bytes usando a regra "comportamento indefinido" para quando não há correspondência.
• Economizou 6 bytes usando pós-incremento em vez de definir 1 após cada loop

Complexidade

Como pode ser visto na versão comentada do código, a complexidade do tempo é linear O(n). Em termos de memória, um máximo de n+1variáveis ​​será atribuído. Então é isso O(n).

Java 8, 82 78 76 bytes Não é mais viável, 75 67 64 bytes abaixo na edição

Como uma função lambda:

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

Provavelmente pode ser feito muito menor, isso foi muito rápido.

Explicação:

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
}

*Editar*

75 67 64 bytes usando a estratégia de negação:

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

Experimente online!

(-3 bytes graças a @Nevay)

Explicação:

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 sobre a matriz, negando manter o controle. Se não houver enganos, apenas atropele e gera um erro.

Ambos trabalham com O (n) tempo e O (n) complexidade do espaço.

Braquilog , 5 bytes

a⊇=bh

Experimente online!

Explicação

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.

O adfix interno alista primeiro todos os prefixos em ordem crescente de comprimento e, em seguida, sufixos em ordem decrescente de comprimento. Assim, a saída é produzida pelo prefixo mais curto que permite, se houver. Se um prefixo não tiver duplicatas, o restante do programa falhará, pois todas as subsequências de elementos iguais têm comprimento 1 e o primeiro elemento de sua cauda não existe. Se um prefixo tiver um elemento repetido, podemos escolher a subsequência comprimento-2 que contém ambos, e o programa retornará o último.

C #, 145 bytes

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

Provavelmente uma maneira muito mais curta de fazer isso em C # com um loop simples, mas eu queria tentar com o Linq.

Experimente online!

Versão completa / formatada:

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();
        }
    }
}

Haskell , 78 69 bytes

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

Experimente online!

Guardado 9 bytes graças a @nimi

Um caminho básico através da lista. Se o elemento atual ainda não foi visto ( i<0) e está na lista de acumuladores ( elem x a), armazene o índice atual. Senão, mantenha o índice -1. De qualquer forma, adicione o elemento atual à lista do acumulador.

Edição : Eu não li a pergunta com atenção suficiente: este código gera o índice do segundo elemento de um elemento duplicado.

Python 2, 71 65 bytes

Devoluções None se não houver elemento duplicado

Edit: -6 bytes graças a @ musicman523

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

Experimente online!

O (n) complexidade do tempo, O (n) complexidade do espaço, O (1) espaço auxiliar.

Como a lista de entrada usa espaço O (n) , a complexidade do espaço é limitada por isso. O que significa que não podemos ter uma complexidade de espaço menor que O (n)

Modifica a lista original, se isso não for permitido, poderíamos fazê-lo na mesma complexidade com 129 bytes

Explicação

Como todo elemento é maior que 0 e menor ou igual ao tamanho da lista, a lista possui para cada elemento a, um elemento no índice a - 1 (0 indexado). Exploramos isso dizendo que, se o elemento no índice i é negativo, já o vimos antes.

Para cada elemento a na lista n, deixamos que seja negativo o valor absoluto de a. (Deixamos que seja negativo, já que o python pode indexar listas com índices negativos, e seria necessário fazê-lo u=abs(a)-1 ) Se o elemento no índice u da lista for negativo, já o vimos antes e, portanto, podemos retornar -u (para obter o valor absoluto de a, pois todos os elementos são positivos) . Caso contrário, definimos o elemento no índice u como negativo, para lembrar que vimos um elemento de valor a antes.

Gelatina , 4 bytes

ŒQi0

Experimente online!

Caso todos os elementos sejam únicos, isso retornará 0(comportamento indefinido).