Dada una matriz a que contiene solo números en el rango de 1 a una longitud, encuentre el primer número duplicado para el cual la segunda aparición tiene el índice mínimo. En otras palabras, si hay más de 1 números duplicados, devuelva el número para el que la segunda aparición tiene un índice más pequeño que la segunda aparición del otro número. Si no hay tales elementos, su programa / función puede resultar en un comportamiento indefinido.

Ejemplo:

Para a = [2, 3, 3, 1, 5, 2], la salida debe ser firstDuplicate(a) = 3.

Hay 2 duplicados: los números 2 y 3. La segunda aparición de 3 tiene un índice más pequeño que la segunda aparición de 2, por lo que la respuesta es 3.

Para a = [2, 4, 3, 5, 1], la salida debe ser firstDuplicate(a) = -1.

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

BONIFICACIÓN: ¿Puedes resolverlo en O (n) complejidad de tiempo y O (1) complejidad de espacio adicional?

Python 2 , 34 bytes

O (n ² ) tiempo, O (n) espacio

^{¡Ahorré 3 bytes gracias a @vaultah, y 3 más de @xnor!}

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

Pruébalo en línea!

JavaScript (ES6), 47 36 31 25 bytes

Guardado 6 bytes gracias a ThePirateBay

Devuelve undefinedsi no existe una solución.

Complejidad del tiempo: O (n) :-)
Complejidad del espacio: O (n) :-(

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

¿Cómo?

Realizamos un seguimiento de los valores ya encontrados guardándolos como nuevas propiedades de la matriz original a mediante el uso de números negativos. De esta manera, no pueden interferir con las entradas originales.

Manifestación

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&

¡La capacidad de coincidencia de patrones de Mathematica es genial!

Devuelve el original Listpara una entrada no válida.

Explicación

#/.

En la entrada, reemplace ...

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

A Listcon un elemento duplicado, con 0 o más elementos antes, entre y después de los duplicados ...

... :>a

Con el elemento duplicado.

Jalea , 5 bytes

Ṛœ-QṪ

Pruébalo en línea!

Cómo 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[]

Pruébalo en línea! Se bloquea si no se encuentra ningún duplicado.

Jalea , 6 bytes

xŒQ¬$Ḣ

Pruébalo en línea!

Devuelve el primer duplicado, o 0 si no hay duplicado.

Explicación

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

Japt , 7 bytes

æ@bX ¦Y

¡Pruébelo en línea!

Explicación

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

¡Pruébelo en línea!

Explicación

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

Pyth, 5 bytes

h.-Q{

Banco de pruebas

Elimine de Q la primera aparición de cada elemento en Q, luego devuelva el primer elemento.

Dyalog APL, 27 24 20 19 13 12 11 bytes

⊢⊃⍨0⍳⍨⊢=⍴↑∪

¡Ahora modificado para no depender de v16! Pruébalo en línea!

¿Cómo? (Con entrada N )

• ⊢⊃⍨...- N en este índice:
  • ⍴↑∪- N con duplicados eliminados, acolchado a la derecha 0para encajar N
  • ⊢=- Igualdad entre elementos con N
  • 0⍳⍨- Índice de la primera 0. ``

Python 3 , 94 92 bytes

O (n) tiempo y O (1) memoria 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

Pruébalo en línea!

Fuente del algoritmo .

Explicación

La idea básica del algoritmo es ejecutar cada elemento de izquierda a derecha, realizar un seguimiento de los números que han aparecido y devolver el número al llegar a un número que ya apareció, y devolver -1 después de atravesar cada elemento.

Sin embargo, utiliza una forma inteligente de almacenar los números que han aparecido sin usar memoria adicional: almacenarlos como el signo del elemento indexado por el número. Por ejemplo, puedo representar el hecho de que 2y 3ya ha aparecido por tener a[2]y a[3]negativo, si la matriz es 1-indexado.

Perl 6 , 13 bytes

*.repeated[0]

Intentalo

Explicación

• El *está en una posición de término, por lo que toda la declaración es un lambda WhateverCode .

• El .repeatedes un método que da como resultado cada valor, excepto la primera vez que se vio cada valor.

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

• [0]solo devuelve el primer valor en la Seq .
  Si no hay valor, se devuelve Nil .
  ( Nil es la base de los tipos de Fallo , y todos los tipos tienen su propio valor indefinido, por lo que Nil es diferente de un valor indefinido en la mayoría de los otros idiomas)

Tenga en cuenta que, dado que la implementación de.repeated genera una Seq, eso significa que no comienza a hacer ningún trabajo hasta que solicite un valor, y solo hace suficiente trabajo para generar lo que solicita.
Por lo tanto, sería fácil argumentar que esto tiene en el peor de los casos O (n)  complejidad de tiempo, y en el mejor de los casos O (2)  complejidad de tiempo si el segundo valor es una repetición del primero.
Similarmente se puede decir de la complejidad de la memoria.

APL (Dyalog) , 20 bytes

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

Pruébalo en línea!

2⍴¯1 negativo uno r eshaped en una lista longitud de dos

⎕, obtener entrada (mnemónica: caja de consola) y anteponer eso

n← almacenar eso en n

,\ prefijos de n (literalmente, concatenación acumulativa)

(... )¨ aplique la siguiente función tácita a cada prefijo

 , [es] el enmarañamiento (solo asegura que el prefijo sea una lista)

 ≢ diferente de

 ∪ los elementos únicos [?] (es decir, ¿el prefijo tiene duplicados?)

n/⍨ use eso para filtrar n (elimina todos los elementos hasta el primero para el que se encontró un duplicado)

⊃ elige el primer elemento de ese

APL (Dyalog) , 11 bytes

Según las nuevas reglas , arroja un error si no existen duplicados.

⊢⊃⍨⍬⍴⍳∘≢~⍳⍨

Pruébalo en línea!

⍳⍨ los índices de la primera aparición de cada elemento

~ retirado de

⍳∘≢ de todos los índices

⍬⍴ remodelar eso en un escalar (da cero si no hay datos disponibles)

⊃⍨ usar eso para elegir (da error en cero)

⊢ el argumento

APL, 15

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

Parece que podemos devolver 0 en lugar de -1 cuando no hay duplicados, (gracias Adám por el comentario). Entonces 3 bytes menos.

Un poco de descripción:

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

Como referencia, la solución anterior agregó -1 a la lista al final, por lo que si la lista terminara vacía, contendría -1 y el primer elemento sería -1.

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

Pruébalo en tryapl.org

Retina , 26 24 bytes

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

Pruébalo en línea! Explicación: \b(\d+)\bcoincide con cada número por turno, y luego mira hacia atrás para ver si el número es un duplicado; si es la salida de 1st match !, en lugar del recuento de coincidencias. Desafortunadamente, poner el lookbehind primero no parece funcionar, de lo contrario ahorraría varios bytes. Editar: se agregaron 7 bytes para cumplir con el -1valor de retorno en caso de no coincidencia. Guardado 2 bytes gracias a @MartinEnder.

MATL , 8 bytes

&=Rsqf1)

Da un error (sin salida) si no existe ningún duplicado.

¡Pruébelo en MATL Online!

Explicación

&=   % 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 algunos caracteres de la respuesta de @djhurio, aunque no tengo suficiente reputación para comentar.

J, 17 16 bytes

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

¿Cómo?

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

Pruébalo en línea!

J , 12 bytes

,&_1{~~:i.0:

Pruébalo en línea!

Explicación

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

Solo funciona en ⎕IO←0.

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

Elimine de la lista de índices de los elementos del argumento con un "-1" antepuesto los índices de lista de su protuberancia y luego elija el primero de lo que queda. Si después de la eliminación solo queda un vector vacío, su primer elemento es, por definición, 0, que se utiliza para indexar el argumento extendido que produce el -1 deseado.

Ruby , 28 36 bytes

Entendió mal el desafío la primera vez. O(n)tiempo, O(n)espacio

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

Pruébalo en línea!

Java (OpenJDK 8) , 65 117 109 bytes

Solución 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;}

Nueva solución Se incluyen 19 bytes paraimport java.math.*;

-8 bytes gracias a @Nevay

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

Pruébalo en línea!

Editar

El algoritmo en mi programa original estaba bien, pero el tamaño estático del tipo de datos utilizado significaba que se rompió bastante rápido una vez que el tamaño superó un cierto umbral.

He cambiado el tipo de datos utilizado en el cálculo para aumentar el límite de memoria del programa para acomodar esto (utilizando BigIntegerprecisión arbitraria en lugar de into long). Sin embargo, esto hace discutible si esto cuenta o no como O(1)complejidad espacial.

Dejaré mi explicación a continuación intacta, pero deseo agregar que ahora creo que es imposible lograr O(1)la complejidad del espacio sin hacer algunas suposiciones.

Prueba

Definir Ncomo un entero tal que 2 <= N.

Deje Sser una lista que representa una serie de enteros aleatorios [x{1}, ..., x{N}], donde x{i}tiene la restricción 1 <= x{i} <= N.

La complejidad de tiempo (en notación Big-O) requerida para recorrer esta lista exactamente una vez por elemento es O(n)

El desafío dado es encontrar el primer valor duplicado en la lista. Más específicamente, estamos buscando el primer valor Sque es un duplicado de un elemento anterior en la lista.

Dejar py qser las posiciones de dos elementos en la lista de tal manera que p < qy x{p} == x{q}. Nuestro desafío es encontrar el más pequeño qque satisfaga esas condiciones.

El enfoque obvio para este problema es recorrer en iteración S y verificar si x{i}existe en otra lista T: si x{i}no existe en T, la almacenamos T. Si x{i}existe en T, es el primer valor duplicado y, por lo tanto, el más pequeño q, y como tal lo devolvemos. Esta eficiencia espacial es O(n).

Para lograr O(1)la complejidad del espacio mientras se mantiene la O(n)complejidad del tiempo, tenemos que almacenar información única sobre cada objeto en la lista en una cantidad finita de espacio. Debido a esto, la única forma en que cualquier algoritmo podría funcionar enO(1)la complejidad del espacio es si: 1. A N se le asigna un límite superior correspondiente a la memoria requerida para almacenar el número máximo de valores posibles para un tipo de datos finito en particular. 2. La reasignación de una sola variable inmutable no se cuenta en función de la complejidad, solo el número de variables (una lista son múltiples variables). 3. (Basado en otras respuestas) La lista es (o al menos, los elementos de la lista son) mutables, y el tipo de datos de la lista está preestablecido como un entero con signo, lo que permite que se realicen cambios en los elementos más adelante en la lista sin usar memoria adicional.

1 y 3 requieren supuestos y especificaciones sobre el tipo de datos, mientras que 2 requiere que solo se considere el número de variables para el cálculo de la complejidad del espacio, en lugar del tamaño de esas variables. Si no se acepta ninguno de estos supuestos, sería imposible lograr la O(n)complejidad del tiempo y O(1)la complejidad del espacio.

Explicación

Whoo boy, este tomó un tiempo vergonzosamente largo para pensar un poco de poder mental.

Entonces, ir por la bonificación es difícil. Necesitamos ambos para operar sobre la lista completa exactamente una vez y rastrear qué valores ya hemos iterado sin complejidad de espacio adicional.

La manipulación de bits resuelve esos problemas. Inicializamos nuestro O(1)'almacenamiento', un par de enteros, luego iteramos a través de la lista, OR-on el bit i en nuestro primer entero y almacenamos ese resultado en el segundo.

Por ejemplo, si tenemos 1101, y realizamos una operación OR con 10, obtenemos 1111. Si hacemos otro OR con 10, todavía tenemos 1101.

Ergo, una vez que realizamos la operación OR y terminamos con el mismo número, encontramos nuestro duplicado. Ningún duplicado en la matriz hace que el programa se ejecute y arroje una excepción.

PHP, 56 44 38 32 bytes

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

Corre así:

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

Explicación

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.

Ajustes

• Guardado 12 bytes usando variables en lugar de una matriz
• Se guardaron 6 bytes haciendo uso de la regla de "comportamiento indefinido" para cuando no hay coincidencia.
• Se guardaron 6 bytes usando el incremento posterior en lugar de establecerlo en 1 después de cada ciclo

Complejidad

Como se puede ver en la versión comentada del código, la complejidad del tiempo es lineal O(n). En términos de memoria, n+1se asignará un máximo de variables. Entonces eso es O(n).

Java 8, 82 78 76 bytes Ya no es viable, 75 67 64 bytes a continuación en edición

Como una función lambda:

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

Probablemente se puede hacer mucho más pequeño, esto fue muy rápido.

Explicación:

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 la estrategia de negación:

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

Pruébalo en línea!

(-3 bytes gracias a @Nevay)

Explicación:

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
}

Recorre la matriz, negando el seguimiento. Si no hay engaños, simplemente corre y arroja un error.

Ambos trabajan en O (n) tiempo y O (n) complejidad espacial.

Brachylog , 5 bytes

a⊇=bh

Pruébalo en línea!

Explicación

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.

El adfix incorporado aenumera primero todos los prefijos en orden creciente de longitud, luego los sufijos en orden decreciente de longitud. Por lo tanto, la salida es producida por el prefijo más corto que lo permite, si lo hay. Si un prefijo no tiene duplicados, el resto del programa falla, ya que cada subsecuencia de elementos iguales tiene longitud 1, y el primer elemento de su cola no existe. Si un prefijo tiene un elemento repetido, podemos elegir la subsecuencia de longitud 2 que contiene ambos, y el programa devuelve el ú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;}

Probablemente sea una forma mucho más corta de hacer esto en C # con un bucle simple, pero quería probarlo con Linq.

Pruébalo en línea!

Versión completa / formateada:

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

Pruébalo en línea!

Guardado 9 bytes gracias a @nimi

Una ruta básica a través de la lista. Si el elemento actual aún no se ha visto ( i<0) y está en la lista de acumuladores ( elem x a), guarde el índice actual. De lo contrario, mantenga el índice -1. En cualquier caso, agregue el elemento actual a la lista de acumuladores.

EDITAR : No leí la pregunta con suficiente atención: este código genera el índice del segundo elemento de un elemento duplicado.

Python 2, 71 65 bytes

Devuelve Nonesi no hay elemento duplicado

Editar: -6 bytes gracias a @ musicman523

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

Pruébalo en línea!

O (n) complejidad temporal, O (n) complejidad espacial, O (1) espacio auxiliar.

Como la lista de entrada usa el espacio O (n) , la complejidad del espacio está limitada por esto. Lo que significa que no podemos tener una complejidad espacial menor que O (n)

Modifica la lista original, si esto no está permitido podríamos hacerlo en la misma complejidad con 129 bytes

Explicación

Dado que cada elemento es mayor que 0 y menor o igual que el tamaño de la lista, la lista tiene para cada elemento a, un elemento en el índice a - 1 (0 indexado). Explotamos esto diciendo que si el elemento en el índice i es negativo, lo hemos visto antes.

Para cada elemento a en la lista n, seremos negativos el valor absoluto de a. (Dejamos que sea negativo ya que Python puede indexar listas con índices negativos, y de lo contrario tendríamos que hacerlo u=abs(a)-1 ) Si el elemento en el índice u en la lista es negativo, lo hemos visto antes y, por lo tanto, podemos devolver -u (para obtener el valor absoluto de a, ya que todos los elementos son positivos) . De lo contrario, establecemos que el elemento en el índice u sea negativo, para recordar que hemos visto un elemento de valor a antes.

Jalea , 4 bytes

ŒQi0

Pruébalo en línea!

En caso de que todos los elementos sean únicos, esto devuelve 0(comportamiento indefinido).