Biorąc pod uwagę tablicę, która zawiera tylko liczby w zakresie od 1 do a. Długości, znajdź pierwszą zduplikowaną liczbę, dla której drugie wystąpienie ma minimalny indeks. Innymi słowy, jeśli istnieje więcej niż 1 zduplikowana liczba, zwróć liczbę, dla której drugie wystąpienie ma mniejszy indeks niż drugie wystąpienie drugiej liczby. Jeśli nie ma takich elementów, twój program / funkcja może spowodować niezdefiniowane zachowanie.

Przykład:

Na a = [2, 3, 3, 1, 5, 2]wyjście powinno być firstDuplicate(a) = 3.

Istnieją 2 duplikaty: liczby 2 i 3. Drugie wystąpienie 3 ma mniejszy indeks niż drugie wystąpienie 2, więc odpowiedź to 3.

Na a = [2, 4, 3, 5, 1]wyjście powinno być firstDuplicate(a) = -1.

To jest golf golfowy , więc wygrywa najkrótsza odpowiedź w bajtach.

BONUS: Czy możesz to rozwiązać przy złożoności czasowej O (n) i dodatkowej złożoności przestrzennej O (1)?

Python 2 , 34 bajty

Czas O (n ² ), przestrzeń O (n)

^{Zaoszczędź 3 bajty dzięki @vaultah i 3 więcej z @xnor!}

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

Wypróbuj online!

JavaScript (ES6), 47 36 31 25 bajtów

Zaoszczędź 6 bajtów dzięki ThePirateBay

Zwraca, undefinedjeśli nie ma rozwiązania.

Złożoność czasowa: O (n) :-)
Złożoność przestrzeni: O (n) :-(

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

W jaki sposób?

Śledzimy już napotkane wartości, zapisując je jako nowe właściwości oryginalnej tablicy a za pomocą liczb ujemnych. W ten sposób nie mogą one zakłócać oryginalnych wpisów.

Próbny

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 bajty

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

Możliwość dopasowania wzorców przez Mathematica jest taka fajna!

Zwraca oryginał Listdla nieprawidłowych danych wejściowych.

Wyjaśnienie

#/.

W danych wejściowych zastąp ...

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

A Listze zduplikowanym elementem, z 0 lub więcej elementami przed, pomiędzy i po duplikatach ...

... :>a

Ze zduplikowanym elementem.

Galaretka , 5 bajtów

Ṛœ-QṪ

Wypróbuj online!

Jak to działa

Ṛœ-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 bajtów

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

Wypróbuj online! Awarie, jeśli nie znaleziono duplikatu.

Galaretka , 6 bajtów

xŒQ¬$Ḣ

Wypróbuj online!

Zwraca pierwszy duplikat lub 0, jeśli nie ma duplikatu.

Wyjaśnienie

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 bajtów

æ@bX ¦Y

Przetestuj online!

Wyjaśnienie

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

Alternatywnie:

æ@¯Y øX

Przetestuj online!

Wyjaśnienie

 æ@   ¯ 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 bajtów

h.-Q{

Zestaw testowy

Usuń z Q pierwsze pojawienie się każdego elementu w Q, a następnie zwróć pierwszy element.

Dyalog APL, 27 24 20 19 13 12 11 bajtów

⊢⊃⍨0⍳⍨⊢=⍴↑∪

Teraz zmodyfikowane, aby nie zależeć od wersji 16! Wypróbuj online!

W jaki sposób? (Z wejściem N )

• ⊢⊃⍨...- N o tym indeksie:
  • ⍴↑∪- N z usuniętymi duplikatami, prawy wyściełany, 0aby pasował do N.
  • ⊢=- Równość elementarna z N
  • 0⍳⍨- Indeks pierwszego 0. `

Python 3 , 94 92 bajty

O (n) czas i O (1) dodatkowa pamięć.

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

Wypróbuj online!

Źródło algorytmu .

Wyjaśnienie

Podstawową ideą algorytmu jest przebieganie przez każdy element od lewej do prawej, śledzenie pojawiających się liczb i zwracanie liczby po osiągnięciu liczby, która już się pojawiła, i zwracanie -1 po przejściu przez każdy element.

Jednak wykorzystuje sprytny sposób do przechowywania liczb, które się pojawiły, bez użycia dodatkowej pamięci: do przechowywania ich jako znaku elementu indeksowanego przez liczbę. Na przykład mogę przedstawić fakt, że 2i 3już się pojawił, mając a[2]i a[3]ujemne, jeśli tablica jest indeksowana 1.

Perl 6 , 13 bajtów

*.repeated[0]

Spróbuj

Wyjaśnienie

• *Znajduje się w położeniu Term więc cała wypowiedź jest WhateverCode lambda.

• .repeatedJest to metoda, która powoduje każdej wartości z wyjątkiem po raz pierwszy każda wartość widziano.

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

• [0]zwraca tylko pierwszą wartość w Seq .
  Jeśli nie ma żadnej wartości, zwracane jest zero .
  ( Zero jest podstawą typów awarii , a wszystkie typy mają swoją własną niezdefiniowaną wartość, więc zero różni się od wartości niezdefiniowanej w większości innych języków)

Zauważ, że ponieważ implementacja.repeated generuje Seq , oznacza to, że nie zaczyna wykonywać żadnej pracy, dopóki nie poprosisz o wartość, i wykonuje tylko tyle pracy, aby wygenerować to, o co prosisz.
Łatwo byłoby więc argumentować, że ma ona w najgorszym przypadku  złożoność czasową O (n) , aw najlepszym  razie złożoność czasową O (2), jeśli druga wartość jest powtórzeniem pierwszej.
Podobnie można powiedzieć o złożoności pamięci.

APL (Dyalog) , 20 bajtów

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

Wypróbuj online!

2⍴¯1 Negatywnym R eshaped do długości na listę

⎕, pobierz dane wejściowe (mnemonic: konsola) i do tego dołącz

n← przechowuj to w n

,\ przedrostki n (lit. kumulatywna konkatenacja)

(… )¨ Zastosuj następującą ukrytą funkcję do każdego prefiksu

 , [to] ravel (zapewnia tylko, że prefiks jest listą)

 ≢ różny od

 ∪ unikalne elementy [?] (tj. czy prefiks ma duplikaty?)

n/⍨ użyj tego do filtrowania n (usuwa wszystkie elementy, aż do pierwszego, dla którego znaleziono duplikat)

⊃ wybierz z tego pierwszy element

APL (Dyalog) , 11 bajtów

Zgodnie z nowymi zasadami zgłasza błąd, jeśli nie ma duplikatów.

⊢⊃⍨⍬⍴⍳∘≢~⍳⍨

Wypróbuj online!

⍳⍨ wskaźniki pierwszego wystąpienia każdego elementu

~ usunięte z

⍳∘≢ wszystkich wskaźników

⍬⍴ przekształć to w skalar (daje zero, jeśli żadne dane nie są dostępne)

⊃⍨ użyj tego, aby wybrać (daje błąd na zero)

⊢ argument

APL, 15

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

Wydaje się, że możemy zwrócić 0 zamiast -1, gdy nie ma duplikatów (dziękuję Adámowi za komentarz). A więc 3 bajty mniej.

Trochę opisu:

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

Dla porównania, stare rozwiązanie dodało -1 do listy na końcu, więc jeśli lista skończy się pusta, będzie zawierać -1, a pierwszym elementem będzie -1.

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

Wypróbuj na tryapl.org

Siatkówka , 26 24 bajtów

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

Wypróbuj online! Objaśnienie: \b(\d+)\bdopasowuje kolejno każdą liczbę, a następnie lookbehind sprawdza, czy liczba jest duplikatem; jeśli jest to 1st dopasowanie !wyjściowe, a nie liczba dopasowań. Niestety, umieszczenie lookbehind na pierwszym miejscu nie wydaje się działać, w przeciwnym razie zaoszczędziłoby kilka bajtów. Edycja: Dodano 7 bajtów, aby były zgodne z -1wartością zwracaną przy braku dopasowania. Zaoszczędź 2 bajty dzięki @MartinEnder.

MATL , 8 bajtów

&=Rsqf1)

Daje błąd (bez danych wyjściowych), jeśli nie istnieje duplikat.

Wypróbuj w MATL Online!

Wyjaśnienie

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

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

Odetnij kilka znaków od odpowiedzi @djhurio, ale nie masz wystarczającej reputacji, aby komentować.

J, 17 16 bajtów

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

W jaki sposób?

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

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

Wypróbuj online!

J , 12 bajtów

,&_1{~~:i.0:

Wypróbuj online!

Wyjaśnienie

,&_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 znaków

Działa tylko w ⎕IO←0.

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

Usuń z listy indeksów elementów argumentu poprzedzoną literą „-1” indeksy listy jego nub, a następnie wybierz pierwszy z pozostałych. Jeśli po usunięciu pozostaje tylko pusty wektor, jego pierwszym elementem jest z definicji 0, który służy do indeksowania rozszerzonego argumentu dającego pożądane -1.

Rubinowy , 28 36 bajtów

Za pierwszym razem źle zrozumiałem wyzwanie. O(n)czas, O(n)przestrzeń.

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

Wypróbuj online!

Java (OpenJDK 8) , 65 117 109 bajtów

Poprzednie 65 bajtowe rozwiązanie:

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

Nowe rozwiązanie Uwzględniono 19 bajtówimport java.math.*;

-8 bajtów dzięki @Nevay

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

Wypróbuj online!

Edytować

Algorytm w moim oryginalnym programie był w porządku, ale statyczny rozmiar użytego typu danych oznaczał, że złamał się dość szybko, gdy rozmiar przekroczył określony próg.

Zmieniłem typ danych użyty w obliczeniach, aby zwiększyć limit pamięci programu, aby to uwzględnić (używając BigIntegerdla dowolnej precyzji zamiast intlub long). To jednak sprawia, że ​​dyskusyjne jest, czy liczy się to jako O(1)złożoność przestrzeni.

Wyjaśnienia pozostawiam poniżej nietknięte, ale chciałbym dodać, że obecnie uważam, że niemożliwe jest osiągnięcie O(1)złożoności przestrzeni bez przyjęcia pewnych założeń.

Dowód

Zdefiniuj Njako liczbę całkowitą taką, że 2 <= N.

Niech Sbędzie listą reprezentującą serię losowych liczb całkowitych [x{1}, ..., x{N}], gdzie x{i}ma ograniczenie 1 <= x{i} <= N.

Złożoność czasu (w notacji Big-O) wymagana do iteracji tej listy dokładnie raz na element O(n)

Podane wyzwanie polega na znalezieniu pierwszej zduplikowanej wartości na liście. Mówiąc dokładniej, szukamy pierwszej wartości, Sktóra jest duplikatem poprzedniego elementu na liście.

Niech pi qbyć pozycje dwóch elementów listy takie, że p < qi x{p} == x{q}. Naszym wyzwaniem staje się znalezienie najmniejszego, qktóry spełnia te warunki.

Oczywistym podejściem do tego problemu jest iteracja przez S i sprawdzenie, czy nasz x{i}istnieje na innej liście T: jeśli x{i}nie istnieje T, przechowujemy go T. Jeśli x{i}istnieje T, to jest to pierwsza zduplikowana wartość, a zatem najmniejsza q, i jako taka zwracamy ją. Ta efektywność przestrzeni wynosi O(n).

Aby osiągnąć O(1)złożoność przestrzeni przy jednoczesnym zachowaniu O(n)złożoności czasu, musimy przechowywać unikalne informacje o każdym obiekcie na liście w skończonej ilości miejsca. Z tego powodu jedynym sposobem na działanie dowolnego algorytmuO(1)złożoność przestrzeni występuje, gdy: 1. N otrzymuje górną granicę odpowiadającą pamięci wymaganej do przechowywania maksymalnej liczby możliwych wartości dla określonego skończonego typu danych. 2. Ponowne przypisanie jednej niezmiennej zmiennej nie jest liczone do złożoności, a jedynie liczba zmiennych (lista zawiera wiele zmiennych). 3. (Na podstawie innych odpowiedzi) Lista jest (lub przynajmniej elementy listy są) zmienne, a typ danych listy jest wstępnie ustawiony jako liczba całkowita ze znakiem, co umożliwia wprowadzanie zmian w elementach znajdujących się dalej na liście bez użycia dodatkowej pamięci.

1 i 3 wymagają zarówno założeń, jak i specyfikacji dotyczących typu danych, a 2 wymaga, aby do obliczenia złożoności przestrzeni brana była pod uwagę tylko liczba zmiennych, a nie wielkość tych zmiennych. Jeśli żadne z tych założeń nie zostanie zaakceptowane, osiągnięcie O(n)złożoności czasowej i O(1)złożoności przestrzeni byłoby niemożliwe .

Wyjaśnienie

Whoo boy, zajęło to kłopotliwie dużo czasu, by wymyślić odrobinę mocy mózgu.

Tak więc zdobycie bonusu jest trudne. Obaj musimy dokładnie operować na całej liście i śledzić wartości, które już iterowaliśmy, bez dodatkowej złożoności przestrzeni.

Manipulowanie bitami rozwiązuje te problemy. Inicjujemy nasze O(1)„przechowywanie”, parę liczb całkowitych, a następnie iterujemy listę, LUB-i-ity bit w naszej pierwszej liczbie całkowitej i zapisujemy ten wynik na drugim.

Na przykład, jeśli mamy 1101i wykonujemy operację LUB 10, otrzymujemy 1111. Jeśli zrobimy kolejną operację OR 10, nadal mamy 1101.

Ergo, kiedy wykonamy operację OR i skończymy z tym samym numerem, znaleźliśmy nasz duplikat. Brak duplikatów w tablicy powoduje, że program uruchamia się i zgłasza wyjątek.

PHP, 56 44 38 32 bajty

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

Uruchom tak:

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

Wyjaśnienie

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.

Poprawki

• Zaoszczędzono 12 bajtów, używając zmiennych zamiast tablicy
• Zaoszczędzono 6 bajtów, stosując regułę „niezdefiniowane zachowanie” w przypadku braku dopasowania.
• Zaoszczędzono 6 bajtów, używając przyrostu zamiast ustawiania na 1 po każdej pętli

Złożoność

Jak można zauważyć w skomentowanej wersji kodu, złożoność czasowa jest liniowa O(n). Pod względem pamięci n+1zostanie przypisanych maksimum zmiennych. Więc to jest O(n).

Java 8, 82 78 76 bajtów Nie jest już wykonalne, 75 67 64 bajtów poniżej w edycji

Jako funkcja lambda:

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

Prawdopodobnie można go znacznie zmniejszyć, to było bardzo szybkie.

Wyjaśnienie:

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
}

*Edytować*

75 67 64 bajtów przy użyciu strategii negacji:

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

Wypróbuj online!

(-3 bajty dzięki @Nevay)

Wyjaśnienie:

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
}

Pętle nad tablicą, negując śledzenie. Jeśli nie ma duplikatów, po prostu przejeżdża i generuje błąd.

Oba działają na złożoność czasu O (n) i przestrzeni O (n).

Brachylog , 5 bajtów

a⊇=bh

Wypróbuj online!

Wyjaśnienie

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.

Wbudowany adfiks awyświetla najpierw wszystkie prefiksy w kolejności rosnącej długości, a następnie sufiksy w kolejności malejącej długości. Zatem dane wyjściowe są wytwarzane przez najkrótszy prefiks, który pozwala na to, jeśli istnieje. Jeśli prefiks nie ma duplikatów, reszta programu zawiedzie, ponieważ każdy podsekwencja równych elementów ma długość 1, a pierwszy element jego ogona nie istnieje. Jeśli przedrostek ma powtarzający się element, możemy wybrać podsekwencję długości 2 zawierającą oba te elementy, a program zwraca ten drugi.

C #, 145 bajtów

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

Prawdopodobnie o wiele krótszy sposób, aby to zrobić w C # za pomocą prostej pętli, ale chciałem spróbować z Linq.

Wypróbuj online!

Wersja pełna / sformatowana:

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 bajtów

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

Wypróbuj online!

Zaoszczędzono 9 bajtów dzięki @nimi

Podstawowa ścieżka przez listę. Jeśli bieżący element nie był jeszcze widoczny ( i<0) i znajduje się na liście akumulatorów ( elem x a), zapisz bieżący indeks. W przeciwnym razie zachowaj indeks -1. W każdym razie dodaj bieżący element do listy akumulatorów.

EDYCJA : Nie przeczytałem pytania wystarczająco uważnie: ten kod wyświetla indeks drugiego elementu zduplikowanego elementu.

Python 2, 71 65 bajtów

Zwraca, Nonejeśli nie ma duplikatu elementu

Edycja: -6 bajtów dzięki @ musicman523

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

Wypróbuj online!

O (n) złożoność czasu, O (n) złożoność przestrzeni, O (1) przestrzeń pomocnicza.

Ponieważ lista wejściowa wykorzystuje przestrzeń O (n) , złożoność przestrzeni jest przez to ograniczona. Oznacza to, że nie możemy mieć mniejszej złożoności przestrzeni niż O (n)

Zmienia oryginalną listę, jeśli nie jest to dozwolone, moglibyśmy to zrobić z tą samą złożonością przy 129 bajtach

Wyjaśnienie

Ponieważ każdy element jest większy od 0 i mniejszy lub równy rozmiarowi listy, lista ma dla każdego elementu a element na indeks a - 1 (0 indeksowany). Wykorzystujemy to, mówiąc, że jeśli element o indeksie i jest ujemny, to widzieliśmy go wcześniej.

Dla każdego elementu a na liście n, pozwalamy ci być ujemną wartością bezwzględną a. (Dajemy, aby było ujemne, ponieważ Python może indeksować listy z indeksami ujemnymi, a w innym przypadku musielibyśmy to zrobić u=abs(a)-1 ). Jeśli element o indeksie u na liście jest ujemny, widzieliśmy go wcześniej i dlatego możemy zwrócić -u (aby uzyskać wartość bezwzględna a, ponieważ wszystkie elementy są dodatnie) . W przeciwnym razie ustawiamy element przy indeksie u na wartość ujemną, aby pamiętać, że wcześniej widzieliśmy element wartości.

Galaretka , 4 bajty

ŒQi0

Wypróbuj online!

W przypadku, gdy wszystkie elementy są unikalne, zwraca to 0(niezdefiniowane zachowanie).