Suchen Sie das erste duplizierte Element

39

Suchen Sie bei einem Array a, das nur Zahlen im Bereich von 1 bis a.length enthält, die erste doppelte Zahl, für die das zweite Vorkommen den minimalen Index hat. Mit anderen Worten, wenn es mehr als eine doppelte Zahl gibt, geben Sie die Zahl zurück, für die das zweite Vorkommen einen kleineren Index hat als das zweite Vorkommen der anderen Zahl. Wenn es keine solchen Elemente gibt, kann Ihr Programm / Ihre Funktion zu undefiniertem Verhalten führen.

Beispiel:

Für a = [2, 3, 3, 1, 5, 2]sollte die Ausgabe sein firstDuplicate(a) = 3.

Es gibt 2 Duplikate: Nummer 2 und 3. Das zweite Vorkommen von 3 hat einen kleineren Index als das zweite Vorkommen von 2, daher lautet die Antwort 3.

Für a = [2, 4, 3, 5, 1]sollte die Ausgabe sein firstDuplicate(a) = -1.

Das ist , also gewinnt die kürzeste Antwort in Bytes.

BONUS: Können Sie es in O (n) Zeitkomplexität und O (1) zusätzlicher Raumkomplexität lösen?

Jeanderson Candido
quelle
Kommentare sind nicht für längere Diskussionen gedacht. Diese Unterhaltung wurde in den Chat verschoben .
Martin Ender

Antworten:

15

Python 2 , 34 Bytes

O (n 2 ) Zeit, O (n) Raum

3 Bytes gespart dank @vaultah und 3 weitere von @xnor!

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

Probieren Sie es online!

musicman523
quelle
1
Es sieht aus wie lambda l:l[map(l.remove,set(l))<0]Arbeiten, obwohl die Reihenfolge der Auswertung seltsam ist.
Xnor
Dies wird nicht zurückgegeben, -1wenn keine Duplikate ohne den 'Fußzeilencode' gefunden werden. Zählt dieser Code nicht zu den Bytes? Ich bin neu im Codieren von Golf, tut mir leid, wenn es eine grundlegende Frage ist!
Chris_Rands
@Chris_Rands Unter der Frage fragte der Musiker, ob die Ausnahme in Ordnung ist, statt -1, und OP sagte, dass sie in Ordnung ist und die Antwort des Musikers eine Ausnahme auslöst.
LiefdeWen
Ich habe eine Weile gebraucht, um das herauszufinden. Gut gespielt. Es ist wirklich clever, das 0. Element von l nach dem Ändern der Bedingung zu verwenden.
Thoth19
Gewährleistet Python die zeitliche und räumliche Komplexität von Standard-Bibliotheksfunktionen wie set.remove?
Draconis
11

JavaScript (ES6), 47 36 31 25 Byte

6 Bytes gespart dank ThePirateBay

Gibt zurück, undefinedwenn keine Lösung vorhanden ist.

Zeitkomplexität: O (n) :-)
Raumkomplexität: O (n) :-(

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

Wie?

Wir verfolgen bereits festgestellte Werte, indem wir sie unter Verwendung negativer Zahlen als neue Eigenschaften des ursprünglichen Arrays a speichern . Auf diese Weise können sie möglicherweise nicht die ursprünglichen Einträge stören.

Demo

Arnauld
quelle
25 Bytes:a=>a.find(c=>!(a[-c]^=1))
@ThePirateBay Oh, natürlich. Vielen Dank!
Arnauld
Beachten Sie nur, dass Objekte in JavaScript möglicherweise nicht als Hash-Tabelle implementiert sind. Die zeitliche Komplexität beim Zugriff auf Schlüssel eines Objekts ist möglicherweise nicht O (1).
Dienstag,
6

Mathematica, 24 Bytes

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

Mathematics Pattern Matching-Fähigkeit ist so cool!

Gibt das Original Listfür ungültige Eingaben zurück.

Erläuterung

#/.

Ersetzen Sie in der Eingabe ...

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

A Listmit einem doppelten Element, mit 0 oder mehr Elementen vor, zwischen und nach den doppelten Elementen ...

... :>a

Mit dem doppelten Element.

JungHwan min
quelle
6

Gelee , 5 Bytes

Ṛœ-QṪ

Probieren Sie es online!

Wie es funktioniert

Ṛœ-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.
Dennis
quelle
œ-Entfernt das am weitesten rechts stehende Vorkommen? TIL
Erik der Outgolfer
Dies scheint nicht -1für keine Duplikate zurückzukehren. Das Auslösen einer Ausnahme ist gemäß OP in Ordnung, aber ich bin nicht sicher, ob dies der Fall 0ist, obwohl es nicht im Bereich liegt.
Erik der Outgolfer
4

Gelee , 6 Bytes

xŒQ¬$Ḣ

Probieren Sie es online!

Gibt das erste Duplikat zurück oder 0, wenn es kein Duplikat gibt.

Erläuterung

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
Meilen
quelle
Es ist Golfier zu verwenden Indizierung wie folgt aus : ŒQi0ị.
Erik der Outgolfer
@EriktheOutgolfer Wenn keine Duplikate vorhanden sind, wird i00 zurückgegeben. Dabei wird der letzte Wert der Eingabe anstelle von 0 indiziert und zurückgegeben.
Meilen
4

Japt , 7 Bytes

æ@bX ¦Y

Online testen!

Erläuterung

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

Alternative:

æ@¯Y øX

Online testen!

Erläuterung

 æ@   ¯ 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
ETHproductions
quelle
4

Pyth, 5 Bytes

h.-Q{

Testsuite

Entfernen Sie aus Q das erste Erscheinungsbild jedes Elements in Q und geben Sie dann das erste Element zurück.

isaacg
quelle
@ LuisMendo Ok, danke. Entschuldigung für die Verwirrung, ich sollte lesen lernen ...
Mr. Xcoder
@ Mr.Xcoder Nein, es ist die Schuld des OP. Diese Information sollte im Aufforderungstext stehen, aber nur in einem Kommentar
Luis Mendo
4

Dyalog APL, 27 24 20 19 13 12 11 Bytes

⊢⊃⍨0⍳⍨⊢=⍴↑∪

Jetzt geändert, um nicht von v16 abzuhängen! Probieren Sie es online!

Wie? (Mit Eingang N )

  • ⊢⊃⍨...- N bei diesem Index:
    • ⍴↑∪- N mit entfernten Duplikaten, rechts gepolstert, um 0zu passen N
    • ⊢= - Elementweise Gleichheit mit N
    • 0⍳⍨- Index der ersten 0. `
Zacharý
quelle
egal, ich habe die Frage falsch verstanden.
Uriel
Tut mir leid, dass ich Sie in die Irre geführt habe. Ich habe die Frage auch falsch verstanden.
Meilen
Sieht aus wie 36 Bytes für mich.
Adám
Oh Gott, Iota Underbar ist nicht dabei ⎕AV, oder?
Zacharý
@ Zacharý Richtig, Classic übersetzt es ⎕U2378 beim Laden. Probieren Sie es online!
Adám
3

Python 3 , 94 92 Bytes

O (n) Zeit und O (1) zusätzlicher Speicher.

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

Probieren Sie es online!

Quelle des Algorithmus .

Erläuterung

Die Grundidee des Algorithmus besteht darin, jedes Element von links nach rechts zu durchlaufen, die aufgetretenen Zahlen zu verfolgen und die Zahl bei Erreichen einer bereits aufgetretenen Zahl zurückzugeben und nach dem Durchlaufen jedes Elements -1 zurückzugeben.

Es verwendet jedoch eine clevere Methode, um die angezeigten Zahlen zu speichern, ohne zusätzlichen Speicherplatz zu belegen: Sie werden als Vorzeichen des durch die Zahl indizierten Elements gespeichert. Zum Beispiel kann ich die Tatsache darstellen, dass 2und 3bereits mit a[2]und a[3]negativ erschienen ist, wenn das Array 1-indiziert ist.

Undichte Nonne
quelle
Was würde dies für iwo a [i]> n tun ?
Downgoat
@ Downgoat las die Frage noch einmal.
Undichte Nonne
Die Frage sagt 1zu a.length, aber für a [i] = a.length würde dies nicht über die Grenzen hinausgehen?
Downgoat
@ Downgoatt=abs(a[i])-1=a.length-1
Leaky Nun
3

Perl 6 , 13 Bytes

*.repeated[0]

Versuch es


Erläuterung

  • Das *ist in einer Zeitposition , so dass die ganze Aussage a WhateverCode Lambda.

  • Dies .repeatedist eine Methode, die zu jedem Wert führt, mit Ausnahme des ersten Males, bei dem jeder Wert angezeigt wurde.

    say [2, 3, 3, 3, 1, 5, 2, 3].repeated.perl; # (3, 3, 2, 3).Seq
    #   (      3, 3,       2, 3).Seq
  • [0]Liefert nur den ersten Wert in der Seq .
    Wenn es keinen Wert gibt, wird Nil zurückgegeben.
    ( Nil ist die Basis der Ausfallarten und alle Arten sind , ihre eigenen nicht definierten Wert, so Nil anders als einen nicht definierten Wert in den meisten anderen Sprachen)


Beachten Sie, dass seit der Implementierung von.repeated ein Seq generiert wird , das bedeutet, dass keine Arbeit anfängt, bis Sie nach einem Wert fragen, und nur genug Arbeit geleistet wird, um das zu generieren, wonach Sie fragen.
Es ist also leicht zu argumentieren, dass dies im schlimmsten Fall eine  Komplexität von O (n) und im besten Fall eine Komplexität von O (2) aufweist,  wenn der zweite Wert eine Wiederholung des ersten Werts ist.
Ähnliches gilt wahrscheinlich für die Speicherkomplexität.

Brad Gilbert b2gills
quelle
3

APL (Dyalog) , 20 Bytes

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

Probieren Sie es online!

2⍴¯1 negative r eshaped in eine längen zwei Listen

⎕, get input (mnemonic: console box) und davor stellen

n← Speichern Sie das in n

,\ Präfixe von n (lit. kumulative Verkettung)

( Wenden Sie auf jedes Präfix die folgende implizite Funktion an

, [is] the ravel (stellt nur sicher, dass das Präfix eine Liste ist)

 anders als

 die eindeutigen Elemente [?] (dh hat das Präfix Duplikate?)

n/⍨ benutze das, um n zu filtern (entfernt alle Elemente bis zu dem ersten, für das ein Duplikat gefunden wurde)

 wähle das erste Element aus

Adam
quelle
Wow, du wurdest dreimal geschlagen. Trotzdem +1. Und können Sie eine Erklärung hinzufügen, wie das funktioniert?
Zacharý
@ Zacharý Anscheinend musste ich nur den Ball ins Rollen bringen. Bitte schön.
Adám
@ Zacharý Irgendwann habe ich es geschafft, sie alle zu besiegen .
Adám
3

APL (Dyalog) , 11 Bytes

Nach den neuen Regeln wird ein Fehler ausgegeben, wenn keine Duplikate vorhanden sind.

⊢⊃⍨⍬⍴⍳∘≢~⍳⍨

Probieren Sie es online!

⍳⍨ die Indizes des ersten Auftretens jedes Elements

~ entfernt von

⍳∘≢ aller Indizes

⍬⍴ verwandle das in einen Skalar (ergibt Null, wenn keine Daten verfügbar sind)

⊃⍨ wähle damit aus (gibt Fehler auf Null)

 das Argument

Adam
quelle
Nun ja, wenn die Regeln geändert werden, können Sie sie natürlich alle schlagen!
Zacharý
Nun, ich habe dich gefesselt.
Zacharý
3

APL, 15

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

Scheint, als könnten wir 0 statt -1 zurückgeben, wenn es keine Duplikate gibt (danke Adám für den Kommentar). Also 3 Bytes weniger.

Ein bisschen Beschreibung:

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

Als Referenz fügte die alte Lösung -1 zur Liste am Ende hinzu. Wenn die Liste leer wäre, würde sie stattdessen -1 enthalten und das erste Element wäre -1.

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

Probieren Sie es auf tryapl.org

Moris Zucca
quelle
Sie können eine Null zurück statt¯1 , so {⊃⍵[(⍳⍴⍵)~⍵⍳⍵]}tun sollten.
Adám
3

Retina , 26 24 Bytes

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

Probieren Sie es online! Erläuterung: \b(\d+)\bStimmt nacheinander mit jeder Zahl überein, und dann prüft der Lookbehind, ob es sich bei der Zahl um ein Duplikat handelt. Wenn dies der 1Fall ist !, wird die erste Übereinstimmung ausgegeben und nicht die Anzahl der Übereinstimmungen. Leider scheint es nicht zu funktionieren, das Lookbehind an die erste Stelle zu setzen, da es sonst mehrere Bytes einspart. Bearbeiten: 7 Bytes hinzugefügt, um dem -1Rückgabewert bei keiner Übereinstimmung zu entsprechen. 2 Bytes dank @MartinEnder gespart.

Neil
quelle
2
Für den Rekord wird der Lookaround nicht zurückverfolgen. Dies verhindert, dass dies funktioniert, wenn Sie versuchen, es vorher zu platzieren. Ich habe diesen Fehler oft gemacht und Martin korrigiert mich immer.
FryAmTheEggman
Ich habe 30 Bytes mit einem Lookahead anstelle eines Lookbehind. Außerdem besagen die Regeln jetzt, dass Sie nicht zurückkehren müssen -1.
Value Ink
@ ValueInk Aber die richtige Antwort für diesen Testfall ist 3 ...
Neil
OH. Ich habe die Herausforderung falsch verstanden, whoops
Value Ink
2

MATL , 8 Bytes

&=Rsqf1)

Gibt einen Fehler (ohne Ausgabe) aus, wenn kein Duplikat vorhanden ist.

Probieren Sie es bei MATL Online!

Erläuterung

&=   % 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
Luis Mendo
quelle
2

R, 34 Bytes

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

Schneiden Sie ein paar Zeichen von der Antwort von @djhurio ab, haben Sie aber nicht genug Ruf, um einen Kommentar abzugeben.

RoryT
quelle
oh ... ich habe diese Antwort nicht gesehen; Dies ist gut für die vorherige Spezifikation, wenn fehlende Werte erforderlich sind, -1aber mit der neuen Spezifikation konnte ich noch mehr Golf spielen. Dies ist immer noch solide und es ist ein anderer Ansatz als er, also gebe ich dir +1!
Giuseppe
2

J, 17 16 Bytes

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

Wie?

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

R , 28 Bytes

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

Probieren Sie es online!

Djhurio
quelle
Ich denke, Sie können jetzt NAnach fehlenden Werten zurückkehren, da sich die Spezifikation geändert hat. so (x=scan())[duplicated(x)][1]ist vollkommen gültig.
Giuseppe
2

J , 12 Bytes

,&_1{~~:i.0:

Probieren Sie es online!

Erläuterung

,&_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
Meilen
quelle
2

Dyalog APL Classic, 18 Zeichen

Funktioniert nur in ⎕IO←0.

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

Entfernen Sie aus der Liste der Indizes der Elemente des Arguments mit einem vorangestellten "-1" die Listenindizes seines Nubs und wählen Sie dann den ersten der verbleibenden Indizes aus. Wenn nach dem Entfernen nur ein leerer Vektor übrig bleibt, ist sein erstes Element per Definition 0, das verwendet wird, um das erweiterte Argument zu indizieren, das das gewünschte -1 ergibt.

lstefano
quelle
Ähm ... was ist mit den zufälligen führenden Leerzeichen? +1 für mich um ein Byte outgolfing .
Zacharý
Sie können einen Fehler auslösen, anstatt ihn zurückzugeben¯1 , damit Sie ihn entfernen ¯1,und verwenden können ⎕IO←1.
Adám
2

Rubin , 28 36 Bytes

Ich habe die Herausforderung das erste Mal missverstanden. O(n)Zeit, O(n)Raum.

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

Probieren Sie es online!

Wert Tinte
quelle
2

Java (OpenJDK 8) , 65 117 109 Bytes

Bisherige 65-Byte-Lösung:

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

Neue Lösung. Für sind 19 Bytes enthaltenimport java.math.*;

-8 Bytes dank @Nevay

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

Probieren Sie es online!

Bearbeiten

Der Algorithmus in meinem ursprünglichen Programm war in Ordnung, aber die statische Größe des verwendeten Datentyps bedeutete, dass er ziemlich schnell kaputt ging, sobald die Größe einen bestimmten Schwellenwert überschritt.

Ich habe den in der Berechnung verwendeten Datentyp geändert, um das Speicherlimit des Programms zu erhöhen, um dies zu berücksichtigen (mit BigIntegerwillkürlicher Genauigkeit anstelle von intoder long). Dies macht es jedoch fraglich, ob dies gilt oder nichtO(1) Raumkomplexität .

Ich werde meine Erklärung im Folgenden intakt lassen, aber ich möchte hinzufügen, dass ich jetzt glaube, dass es unmöglich ist, dies zu erreichen O(1) Raumkomplexität , ohne einige Annahmen zu .

Beweis

Definieren Sie Nals Ganzzahl, so dass2 <= N .

Sei Seine Liste, die eine Reihe zufälliger Ganzzahlen darstellt [x{1}, ..., x{N}], für x{i}die die Einschränkung gilt1 <= x{i} <= N .

Die Zeitkomplexität (in Big-O-Notation), die erforderlich ist, um diese Liste genau einmal pro Element zu durchlaufen, beträgt O(n)

Die Herausforderung besteht darin, den ersten doppelten Wert in der Liste zu finden. Insbesondere suchen wir nach dem ersten Wert S, der ein Duplikat eines vorherigen Elements in der Liste ist.

Lassen Sie pund qdie Positionen von zwei Elementen in der Liste sein, so dass p < qund x{p} == x{q}. Unsere Herausforderung besteht darin, die kleinste zu finden q, die diese Bedingungen erfüllt.

Der offensichtliche Ansatz für dieses Problem besteht darin, S zu durchlaufen und zu prüfen, ob unsere x{i}in einer anderen Liste vorhanden ist T: Wenn x{i}sie nicht in vorhanden ist T, speichern wir sie in T. Wenn x{i}in vorhanden ist T, ist dies der erste doppelte Wert und daher der kleinste q, und wir geben ihn als solchen zurück. Diese Raumeffizienz istO(n) .

Um O(1)Raumkomplexität bei gleichzeitiger Aufrechterhaltung der O(n)Zeitkomplexität zu erreichen, müssen wir eindeutige Informationen zu jedem Objekt in der Liste auf einer begrenzten Fläche speichern. Aus diesem Grund ist dies die einzige Möglichkeit, mit der ein Algorithmus ausgeführt werden kannO(1)Die Raumkomplexität ist, wenn: 1. N eine Obergrenze gegeben wird, die dem Speicher entspricht, der zum Speichern der maximalen Anzahl möglicher Werte für einen bestimmten endlichen Datentyp erforderlich ist. 2. Die Neuzuweisung einer einzelnen unveränderlichen Variablen wird nicht auf die Komplexität angerechnet, sondern nur auf die Anzahl der Variablen (eine Liste mit mehreren Variablen). 3. (Basierend auf anderen Antworten) Die Liste ist (oder zumindest die Elemente der Liste sind) veränderbar, und der Datentyp der Liste ist als vorzeichenbehaftete Ganzzahl voreingestellt, sodass Änderungen an Elementen in der Liste vorgenommen werden können ohne zusätzlichen Speicher zu verwenden.

1 und 3 erfordern Annahmen und Spezifikationen zum Datentyp, während 2 erfordert, dass nur die Anzahl der Variablen für die Berechnung der Raumkomplexität berücksichtigt wird und nicht die Größe dieser Variablen. Wenn keine dieser Annahmen akzeptiert wird, ist es unmöglich, sowohl O(n)Zeitkomplexität als auch O(1)Raumkomplexität zu erreichen.

Erläuterung

Was für ein Junge, dieser brauchte eine peinlich lange Zeit, um sich ein bisschen Gehirnleistung auszudenken .

Es ist also schwierig, den Bonus zu bekommen. Wir müssen beide die gesamte Liste genau einmal durcharbeiten und verfolgen, welche Werte wir bereits durchlaufen haben, ohne dass zusätzliche Platzkomplexität erforderlich ist .

Bit-Manipulation löst diese Probleme. Wir initialisieren unseren O(1)'Speicher', ein Paar Ganzzahlen, durchlaufen dann die Liste, indem wir das i-te Bit in unserer ersten Ganzzahl ODER-ODER-verknüpfen und dieses Ergebnis in der zweiten speichern.

Wenn wir zum Beispiel haben 1101und eine ODER-Operation mit ausführen 10, erhalten wir 1111. Wenn wir einen anderen OP machen 10, haben wir noch 1101.

Ergo, sobald wir die OP-Operation ausgeführt haben und dieselbe Nummer haben, haben wir unser Duplikat gefunden. Keine Duplikate im Array führen dazu, dass das Programm überläuft und eine Ausnahme auslöst.

Xanderhall
quelle
Auch Ihr zweiter Test umfasst die Nummer 100, aber das ist nicht möglich , da das Array selbst nur 5 ist lang
SCHüLER
Auch dies fehlschlägt , da ein int nicht genügend Speicher haben.
SchoolBoy
@SchoolBoy Guter Fang. Mein einziges Problem ist, dass es anscheinend keine Obergrenze für die Größe des Arrays gibt, sodass ich meinen Code nicht realistisch ändern kann, um Speicherprobleme zu lösen.
Xanderhall
@Xanderhall Stimmt, aber ich fühle mich wie 32 (oder wenn Sie eine lange, 64) Zahlen zu wenig ist: p. In beiden Fällen ist es nur ein Betrug, der Eingabe ein Limit aufzuerlegen, dann den maximal benötigten Speicher zuzuweisen und ihn als O (1) -Speicher zu bezeichnen. Es ist immer noch O (n), da, wenn die Größe der Eingabe zunimmt, dies auch die Obergrenze des Speichers sein würde. Aus diesem Grund denke ich, dass es unmöglich ist, einen O (n) O (1) -Algorithmus zu erstellen
SchoolBoy
@Xanderhall PS Ich nähere mich deiner 65, ich bin bei 67 Bytes: p
SchoolBoy
2

PHP, 56 44 38 32 Bytes

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

Laufen Sie wie folgt:

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

Erläuterung

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.

Optimierungen

  • 12 Byte durch Verwendung von Variablen anstelle eines Arrays gespeichert
  • 6 Bytes gespart, indem die Regel "undefiniertes Verhalten" verwendet wird, wenn keine Übereinstimmung vorliegt.
  • 6 Bytes durch Verwendung von Post-Increment gespeichert, anstatt nach jeder Schleife auf 1 zu setzen

Komplexität

Wie aus der kommentierten Version des Codes hervorgeht, ist die zeitliche Komplexität linear O(n). In Bezug auf den Speicher werden maximal n+1Variablen zugewiesen. Das ist es also O(n).

aross
quelle
Vielen Dank, dass Sie keine seltsame Codierung verwenden. Sie sollten jedoch die error_reportingOption zur Bytezahl hinzufügen (oder verwenden -n, was kostenlos ist).
Titus
Wir waren schon mal hier. PHP Hinweise und Warnungen sind ignorierbar. Ich könnte sie genauso gut weiterleiten /dev/null, was dasselbe ist.
Am
Ich neige dazu, mich an die falschen Kommentare zu erinnern. :) Ist das nicht O (n)?
Titus
Ja, es ist linear
ungefähr
Wie ist das O(1)für zusätzlichen Platz? Sie nO(n)
weisen
2

Java 8, 82 78 76 Bytes Nicht mehr verfügbar, 75 67 64 Bytes unten in Bearbeitung

Als Lambda-Funktion:

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

Wahrscheinlich kann man das viel kleiner machen, das ging sehr schnell.

Erläuterung:

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
}

*Bearbeiten*

75 67 64 Bytes unter Verwendung der Negationsstrategie:

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

Probieren Sie es online!

(-3 Bytes dank @Nevay)

Erläuterung:

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
}

Schleifen über das Array, negieren, um den Überblick zu behalten. Wenn keine Dummköpfe, läuft nur über und wirft einen Fehler.

Beide Arbeiten beschäftigen sich mit der Komplexität von O (n) Zeit und O (n) Raum.

Schüler
quelle
Es ist erwähnenswert, dass dies einer Lambda-Rückkehr zugeordnet werden muss Number, da ia longund a -1ist int.
Jakob
@ Jakob Nicht erforderlich, -1 ist ein Int. Wird automatisch auf ein Long umgewandelt, ohne die Besetzung explizit anzugeben
SchoolBoy
Es wird implizit auf long, aber nicht auf, Longwie es für die Zuordnung des Lambda zu a erforderlich ist, umgewandelt Function. Hast du es getestet? Unabhängig davon kann diese Lösung durch Ihre neue ersetzt werden.
Jakob
Sie können Rohtypen verwenden Set s=new HashSet();, um 7 Bytes zu sparen. (Außerdem: afaik muss der Import von java.util.*;in die Byteanzahl einbezogen werden -> +19 Bytes.) Die return-Anweisung kann sein return++j, die if-Anweisung kann entfernt werden a->{int i=0,j;for(;(a[j=Math.abs(a[i++])-1]*=-1)<0;);return++j;}(-3 Bytes).
Nevay
2

Brachylog , 5 Bytes

a⊇=bh

Probieren Sie es online!

Erläuterung

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.

Das integrierte Adfix alistet zuerst alle Präfixe in aufsteigender Reihenfolge der Länge und dann die Suffixe in absteigender Reihenfolge der Länge auf. Daher wird die Ausgabe mit dem kürzesten Präfix erzeugt, das es zulässt, falls vorhanden. Wenn ein Präfix keine Duplikate enthält, schlägt der Rest des Programms fehl, da jede Teilsequenz gleicher Elemente die Länge 1 hat und das erste Element seines Endes nicht existiert. Wenn ein Präfix ein wiederholtes Element enthält, können wir die Teilsequenz der Länge 2 auswählen, die beide Elemente enthält, und das Programm gibt letztere zurück.

Zgarb
quelle
Eine weitere 5-Byte-Lösung: Hier a⊇Ċ=hwerden nur Teilmengen der Länge 2 betrachtet.
Fatalize
1

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

Wahrscheinlich viel kürzer, um dies in C # mit einer einfachen Schleife zu tun, aber ich wollte es mit Linq versuchen.

Probieren Sie es online!

Voll / Formatierte Version:

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();
        }
    }
}
DerLethalCoder
quelle
Hier ist die einfache Loop-Version. Aber die Linq-Version gefällt mir viel besser.
LiefdeWen
@LiefdeWen Poste es als Antwort :) Obwohl ich Linq normalerweise auch besser mag :) Könnte es mit Linq auch kürzer machen, aber ich bin mir jetzt sicher.
TheLethalCoder
Nein, diese Frage ist überfüllt und ich würde es vorziehen, wenn Sie die Gegenstimmen für diese Frage erhalten.
LiefdeWen
1

Haskell , 78-69 Bytes

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

Probieren Sie es online!

9 Bytes dank @nimi gespeichert

Ein grundlegender Pfad durch die Liste. Wenn das aktuelle Element noch nicht gesehen wurde ( i<0) und sich in der Akkuliste befindet ( elem x a), speichern Sie den aktuellen Index. Ansonsten behalten Sie den Index -1. Fügen Sie in jedem Fall das aktuelle Element zur Akkuliste hinzu.

EDIT : Ich habe die Frage nicht sorgfältig genug gelesen: Dieser Code gibt den Index des zweiten Elements eines doppelten Elements aus.

jferard
quelle
Sie können die Verwendung „Kürzere Conditional“ unsere „für Golf in Haskell Tipps“ : \ ... ->(last$i:[j|i<0,elem x a],x:a). Außerdem: keine Notwendigkeit für die f=, weil unbenannte Funktionen erlaubt sind.
nimi
@nimi danke für den tipp!
jferard
1

Python 2, 71 65 Bytes

Gibt zurück, Nonewenn kein doppeltes Element vorhanden ist

Edit: -6 Bytes dank @ musicman523

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

Probieren Sie es online!

O (n) Zeitkomplexität, O (n) Raumkomplexität, O (1) Hilfsraum.

Da die Eingabeliste den O (n) -Raum verwendet, ist die Raumkomplexität hieran gebunden. Das heißt, wir können keine niedrigere Raumkomplexität als O (n) haben

Ändert die ursprüngliche Liste, wenn dies nicht erlaubt ist, könnten wir es in der gleichen Komplexität mit 129 Bytes tun

Erläuterung

Da jedes Element größer als 0 und kleiner oder gleich der Größe der Liste ist, enthält die Liste für jedes Element a ein Element auf Index a - 1 (0 indiziert). Wir nutzen dies aus, indem wir sagen, wenn das Element bei Index i negativ ist, haben wir es bereits gesehen.

Für jedes Element a in der Liste n sei u der absolute Wert von a negativ. (Wir lassen es negativ sein, da Python Listen mit negativen Indizes indizieren kann und dies andernfalls tun müsste. u=abs(a)-1 ) Wenn das Element am Index u in der Liste negativ ist, haben wir es bereits gesehen und können daher -u zurückgeben (um das zu erhalten) absoluter Wert von a, da alle Elemente positiv sind) . Anderenfalls setzen wir das Element am Index u auf negativ, um uns daran zu erinnern, dass wir bereits ein Element mit dem Wert a gesehen haben.

Halvard Hummel
quelle
Gute Arbeit! 65 Bytes
musicman523
Sind Sie sicher, dass dies O (1) im Speicher ist? Sie verwenden immer noch n Speicherbits, um die bereits besuchten Nummern zu speichern, obwohl sich die Bits im Vorzeichen befinden. Es scheint mir, dass dies O (n) in der Verkleidung ist
Weizen-Zauberer
Technisch verwendet dies den O (n) Raum - die n Vorzeichenbits. Wenn das Array nur Werte zwischen 1und enthalten kann n, wie es angegeben wurde, funktioniert es offensichtlich nicht.
Oliver Ni
Das hängt wirklich nur von der Darstellung ab, die Sie für die Zahlen gewählt haben. Wenn vorzeichenlose Zahlen verwendet werden, ist dies der Hilfsraum O (n) . Wenn vorzeichenbehaftete Zahlen verwendet werden, ist das Vorzeichenbit bereits vorhanden und bedeutet O (1) Hilfsraum.
Halvard Hummel
Da stimme ich dir zu Ich persönlich würde Sie mit vorzeichenbehafteten ganzen Zahlen gleiten lassen, solange Sie das Vorzeichenbit nicht verwendet haben. Es sollte sich um den Algorithmus und nicht um die technischen Details des Systems handeln. Davon abgesehen denke ich, wenn Sie die Vorzeichenbits verwenden wollen, müssen Sie sie zählen. Ich finde diese Antwort ziemlich clever. Wenn ich heute noch Stimmen übrig hätte, würde ich sie erhöhen, um der Abwertung entgegenzuwirken.
Weizen-Zauberer