Trouver le premier élément dupliqué

39

Etant donné un tableau a ne contenant que des nombres compris entre 1 et a.length, trouvez le premier numéro en double pour lequel la deuxième occurrence a l'index minimal. En d'autres termes, s'il y a plus d'un nombre dupliqué, renvoyez le numéro pour lequel la seconde occurrence a un index plus petit que la seconde occurrence de l'autre numéro. Si de tels éléments n'existent pas, votre programme / fonction peut entraîner un comportement non défini.

Exemple:

Pour a = [2, 3, 3, 1, 5, 2], la sortie devrait être firstDuplicate(a) = 3.

Il y a 2 doublons: les nombres 2 et 3. La deuxième occurrence de 3 a un indice plus petit que la deuxième occurrence de 2 le fait, donc la réponse est 3.

Pour a = [2, 4, 3, 5, 1], la sortie devrait être firstDuplicate(a) = -1.

C'est du , donc la réponse la plus courte en octets est gagnante.

BONUS: Pouvez-vous le résoudre en complexité temporelle O (n) et en complexité spatiale O (1)?

Jeanderson Candido
la source
Les commentaires ne sont pas pour une discussion prolongée; cette conversation a été déplacée pour discuter .
Martin Ender

Réponses:

15

Python 2 , 34 octets

O (n 2 ) heure, O (n) espace

Sauvegardé 3 octets grâce à @vaultah et 3 autres de @xnor!

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

Essayez-le en ligne!

musicman523
la source
1
Cela ressemble à des lambda l:l[map(l.remove,set(l))<0]œuvres, même si l'ordre d'évaluation est bizarre.
xnor
Cela ne se produit pas -1lorsqu'aucune copie n'est trouvée sans le "code de pied de page". Ce code ne compte-t-il pas dans les octets? Je suis nouveau sur le code de golf, désolé si c'est une question de base!
Chris_Rands le
@Chris_Rands Sous la question, musicman a demandé si l'exception est acceptable au lieu de -1 et OP a répondu d'accord, et la réponse de musicman lève l'exception.
LiefdeWen
Cela m'a pris un certain temps à comprendre. Bien joué. Obtenir le 0e élément de l en utilisant le conditionnel après l'avoir modifié est vraiment intelligent.
Thoth19
Python garantit-il la complexité temporelle et spatiale des fonctions de bibliothèque standard telles que set.remove?
Draconis
11

JavaScript (ES6), 47 36 31 25 octets

Sauvegardé 6 octets grâce à ThePirateBay

Renvoie undefinedsi aucune solution n'existe.

Complexité temporelle: O (n) :-)
Complexité spatiale: O (n) :-(

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

Comment?

Nous gardons une trace des valeurs déjà rencontrées en les enregistrant comme de nouvelles propriétés du tableau d' origine un en utilisant les numéros négatifs. De cette façon, ils ne peuvent pas interférer avec les entrées originales.

Démo

Arnauld
la source
25 octets:a=>a.find(c=>!(a[-c]^=1))
@ThePirateBay Oh, bien sûr. Merci!
Arnauld
Notez simplement que les objets en JavaScript ne peuvent pas être implémentés en tant que table de hachage. La complexité temporelle de l'accès aux clés de certains objets peut ne pas être O (1).
tsh
6

Mathematica, 24 octets

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

La capacité de correspondance de motifs de Mathematica est tellement cool!

Renvoie l'original Listpour une entrée non valide.

Explication

#/.

Dans l'entrée, remplacez ...

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

A Listavec un élément en double, avec 0 ou plusieurs éléments avant, entre et après les doublons ...

... :>a

Avec l'élément dupliqué.

JungHwan Min
la source
6

Gelée , 5 octets

Ṛœ-QṪ

Essayez-le en ligne!

Comment ça marche

Ṛœ-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
la source
œ-supprime les occurrences les plus à droite? TIL
Erik the Outgolfer
Cela ne semble pas revenir -1sans doublons. Lancer une exception est acceptable selon l'OP mais je ne suis pas sûr si 0c'est même si ce n'est pas dans la plage.
Erik the Outgolfer
4

Gelée , 6 octets

xŒQ¬$Ḣ

Essayez-le en ligne!

Retourne le premier doublon ou 0 s'il n'y a pas de doublon.

Explication

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
milles
la source
Il est Golfier à l' indexation de l' utilisation comme ceci: ŒQi0ị.
Erik the Outgolfer
@EriktheOutgolfer S'il n'y a pas de doublons, i0renverrait 0, où indexerait et renverrait la dernière valeur de l'entrée au lieu de 0.
Miles
4

Japt , 7 octets

æ@bX ¦Y

Testez-le en ligne!

Explication

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

Alternativement:

æ@¯Y øX

Testez-le en ligne!

Explication

 æ@   ¯ 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
la source
4

Pyth, 5 octets

h.-Q{

Suite de tests

Supprime de Q la première apparition de chaque élément de Q, puis retourne le premier élément.

isaacg
la source
@ LuisMendo Ok merci. Désolé de créer de la confusion, je devrais apprendre à lire ...
M. Xcoder le
@ Mr.Xcoder Non, c'est la faute du PO. Cette information devrait être dans le texte du défi, mais juste dans un commentaire
Luis Mendo le
4

Dyalog APL, 27 24 20 19 13 12 11 octets

⊢⊃⍨0⍳⍨⊢=⍴↑∪

Maintenant modifié pour ne pas dépendre de v16! Essayez-le en ligne!

Comment? (Avec entrée N )

  • ⊢⊃⍨...- N à cet index:
    • ⍴↑∪- N avec les doublons enlevés, rembourré à droite 0pour s'adapter à N
    • ⊢=- égalité élémentaire avec N
    • 0⍳⍨- Index du premier 0. `
Zacharý
la source
tant pis, j'ai mal interprété la question. pas assez d'essais cependant ...
Uriel
Désolé de vous avoir induit en erreur, j'ai également mal interprété la question.
miles
Cela ressemble à 36 octets pour moi.
Adám le
Oh mon dieu, iota underbar n'est pas là ⎕AV, hein?
Zacharý
@ Zacharý Droite, Classic le traduit en ⎕U2378 chargement. Essayez-le en ligne!
Adám
3

Python 3 , 94 92 octets

O (n) temps et O (1) mémoire supplémentaire.

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

Essayez-le en ligne!

Source de l'algorithme .

Explication

L'idée de base de l'algorithme est de parcourir chaque élément de gauche à droite, de garder une trace des nombres apparus et de renvoyer le nombre lorsque le nombre atteint est déjà atteint, et de renvoyer -1 après avoir parcouru chaque élément.

Cependant, il utilise un moyen astucieux pour stocker les nombres qui sont apparus sans utiliser de mémoire supplémentaire: pour les stocker en tant que signe de l'élément indexé par le nombre. Par exemple, je peux représenter le fait que 2et 3est déjà apparu en ayant a[2]et a[3]négatif, si le tableau est 1-indexé.

Fuite Nun
la source
Qu'est-ce que cela ferait pour ioù un [i]> n?
Descendre le
@Downgoat a relu la question.
Leaky Nun
La question dit 1a.length mais pour un [i] = a.length cela ne serait-il pas hors limites?
Descendre le
@Downgoatt=abs(a[i])-1=a.length-1
Leaky Nun
3

Perl 6 , 13 octets

*.repeated[0]

L'essayer


Explication

  • Le *est dans une position à terme, donc la déclaration entière est un lambda WhateverCode .

  • Le .repeatedest une méthode qui donne chaque valeur sauf la première fois que chaque valeur est vue.

    say [2, 3, 3, 3, 1, 5, 2, 3].repeated.perl; # (3, 3, 2, 3).Seq
    #   (      3, 3,       2, 3).Seq
  • [0]renvoie simplement la première valeur de la Seq .
    S'il n'y a pas de valeur, Nil est renvoyé.
    ( Nil est la base des types d' échec , et tous les types ont leur propre valeur indéfinie, donc Nil est différent d'une valeur indéfinie dans la plupart des autres langues)


Notez que depuis l’ implémentation de.repeated génère une Seq, cela signifie qu’il ne commence à faire aucun travail tant que vous n’avez pas demandé une valeur et qu’il ne fait que suffisamment de travail pour générer ce que vous demandez.
Il serait donc facile de dire que cela a au pire une  complexité temporelle en O (n) , et au mieux une complexité temporelle en O (2)  si la seconde valeur est une répétition de la première.
On peut probablement en dire autant de la complexité de la mémoire.

Brad Gilbert b2gills
la source
3

APL (Dyalog) , 20 octets

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

Essayez-le en ligne!

2⍴¯1 négatif une r eshaped dans une liste d' ancienneté deux

⎕, obtenir une entrée (mnémonique: console) et y ajouter

n← stocker que dans n

,\ préfixes de n (lit. concaténation cumulative)

( Applique la fonction tacite suivante à chaque préfixe

, [est] le ravel (assure juste que le préfixe est une liste)

 différent de

 les éléments uniques [?] (le préfixe a-t-il des doublons?)

n/⍨ utilisez cela pour filtrer n (supprime tous les éléments jusqu'au premier pour lequel un doublon a été trouvé)

 choisir le premier élément de celui

Adam
la source
Wow, vous avez été battu trois fois. Toujours, +1. Et pouvez-vous ajouter une explication sur la façon dont cela fonctionne?
Zacharý
@ Zacharý Apparemment, j'avais juste besoin de lancer le processus. Voici.
Adám
@ Zacharý Finalement, j'ai réussi à les battre tous .
Adám
3

APL (Dyalog) , 11 octets

Conformément aux nouvelles règles , génère une erreur si aucun doublon n’existe.

⊢⊃⍨⍬⍴⍳∘≢~⍳⍨

Essayez-le en ligne!

⍳⍨ les indices de la première occurrence de chaque élément

~ retiré de

⍳∘≢ de tous les indices

⍬⍴ remodeler cela en un scalaire (donne zéro si aucune donnée n'est disponible)

⊃⍨ utilisez-le pour choisir (donne l'erreur sur zéro)

 l'argument

Adam
la source
Oui, quand les règles sont modifiées, vous pouvez bien sûr toutes les battre!
Zacharý
Eh bien, je t'ai attaché.
Zacharý
3

APL, 15

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

On dirait que nous pouvons renvoyer 0 au lieu de -1 lorsqu'il n'y a pas de doublons (merci Adám pour le commentaire). Donc 3 octets de moins.

Un peu de description:

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

Pour référence, l'ancienne solution ajoutait -1 à la liste à la fin. Ainsi, si la liste était vide, elle contiendrait -1 et le premier élément serait -1.

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

Essayez-le sur tryapl.org

Moris Zucca
la source
Vous pouvez renvoyer un zéro au lieu de¯1 , vous {⊃⍵[(⍳⍴⍵)~⍵⍳⍵]}devriez le faire.
Adám
3

Retina , 26 à 24 octets

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

Essayez-le en ligne! Explication: fait \b(\d+)\bcorrespondre chaque numéro à tour de rôle, puis la recherche précédente cherche à savoir si le nombre est un doublon; si c'est la première 1correspondance qui est !produite, plutôt que le nombre de correspondances. Malheureusement, mettre le lookbehind en premier ne semble pas fonctionner, sinon cela économiserait plusieurs octets. Edit: 7 octets ajoutés pour se conformer à la -1valeur de retour sur aucune correspondance. 2 octets sauvés grâce à @MartinEnder.

Neil
la source
2
Pour mémoire, le lookaround ne reviendra pas. Cela empêche cela de fonctionner si vous essayez de le mettre avant. J'ai commis cette erreur plusieurs fois et Martin me corrige toujours.
FryAmTheEggman le
J'ai obtenu 30 octets en utilisant un lookahead au lieu d'un lookbehind. En outre, les règles indiquent désormais que vous n'avez pas besoin de revenir -1.
Value Ink
@ValueInk Mais la bonne réponse pour ce cas de test est 3 ...
Neil
OH. J'ai mal interprété le défi, whoops
Value Ink
2

MATL , 8 octets

&=Rsqf1)

Donne une erreur (sans sortie) s'il n'y a pas de doublon.

Essayez sur MATL Online!

Explication

&=   % 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
la source
2

R, 34 octets

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

Coupez quelques caractères de la réponse de @djhurio, n’avez pas assez de réputation pour commenter.

RoryT
la source
oh ... je n'ai pas vu cette réponse; c'est bon pour les spécifications précédentes lorsque des valeurs manquantes sont requises, -1mais avec la nouvelle spécification, j'ai réussi à le réduire davantage. C'est encore solide et c'est une approche différente de la façon dont il l'a fait, je vais donc vous donner un +1!
Giuseppe
2

J, 17 16 octets

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

Comment?

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

R , 28 octets

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

Essayez-le en ligne!

Djhurio
la source
Je pense que vous pouvez maintenant retourner NApour les valeurs manquantes car la spécification a changé; donc (x=scan())[duplicated(x)][1]est parfaitement valide.
Giuseppe
2

J , 12 octets

,&_1{~~:i.0:

Essayez-le en ligne!

Explication

,&_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
milles
la source
2

Dyalog APL Classic, 18 caractères

Ne fonctionne que dans ⎕IO←0.

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

Supprimez de la liste des index des éléments de l'argument avec "-1" ajouté la liste des index de son nœud, puis choisissez le premier de ce qui reste. Si, après la suppression, il ne reste qu'un vecteur vide, son premier élément est, par définition, 0 et sert à indexer l'argument étendu produisant le -1 souhaité.

lefefano
la source
Euh ... Qu'est-ce qui se passe avec les espaces aléatoires? +1 pour m'avoir dépassé d' un octet.
Zacharý
Vous pouvez générer une erreur au lieu de revenir¯1 afin de pouvoir supprimer ¯1,et utiliser ⎕IO←1.
Adám
2

Ruby , 28 36 octets

Incompris le défi la première fois. O(n)temps, O(n)espace.

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

Essayez-le en ligne!

Valeur d'encre
la source
2

Java (OpenJDK 8) , 65 117 109 octets

Solution précédente de 65 octets:

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

Nouvelle solution. 19 octets sont inclus pourimport java.math.*;

-8 octets grâce à @Nevay

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

Essayez-le en ligne!

modifier

L'algorithme de mon programme d'origine fonctionnait bien, mais la taille statique du type de données utilisé signifiait qu'il s'était cassé assez rapidement une fois que la taille avait dépassé un certain seuil.

J'ai changé le type de données utilisé dans le calcul pour augmenter la limite de mémoire du programme afin de s'adapter à cela (en utilisant BigIntegerune précision arbitraire au lieu de intou long). Cependant, cela rend discutable si cela compte ou non comme O(1)complexité d'espace.

Je laisserai mon explication ci-dessous intacte, mais j’aimerais ajouter que j’estime maintenant qu’il est impossible de réaliser O(1)la complexité de l’espace sans faire quelques hypothèses.

Preuve

Définir Ncomme un entier tel que 2 <= N.

Soit Sune liste représentant une série d’entiers aléatoires [x{1}, ..., x{N}], où x{i}a la contrainte 1 <= x{i} <= N.

La complexité temporelle (en notation Big-O) requise pour parcourir cette liste exactement une fois par élément est O(n)

Le défi consiste à trouver la première valeur dupliquée dans la liste. Plus précisément, nous recherchons la première valeur Squi est un duplicata d’un élément précédent de la liste.

Laissez pet qsoyez les positions de deux éléments dans la liste tels que p < qet x{p} == x{q}. Notre défi consiste à trouver le plus petit qqui réponde à ces conditions.

L'approche évidente de ce problème est de parcourir S et de vérifier si notre x{i}existe dans une autre liste T: S'il x{i}n'existe pas dans T, nous le stockons dans T. Si x{i}existe dans T, c'est la première valeur en double et donc la plus petite q, et en tant que telle, nous la retournons. Cette efficacité spatiale est O(n).

Pour atteindre O(1)la complexité de l’espace tout en maintenant la O(n)complexité temporelle, nous devons stocker des informations uniques sur chaque objet de la liste dans un espace fini. De ce fait, la seule façon pour un algorithme de fonctionner àO(1)la complexité de l'espace est si: 1. N se voit attribuer une limite supérieure correspondant à la mémoire nécessaire pour stocker le nombre maximal de valeurs possibles pour un type de données fini particulier. 2. La réaffectation d'une seule variable immuable ne compte pas dans la complexité, mais uniquement dans le nombre de variables (une liste étant plusieurs variables). 3. (Basé sur d'autres réponses) La liste est (ou au moins, les éléments de la liste sont) mutable, et le type de données de la liste est prédéfini comme un entier signé, ce qui permet d'apporter des modifications aux éléments plus loin dans la liste. sans utiliser de mémoire supplémentaire.

1 et 3 nécessitent à la fois des hypothèses et des spécifications sur le type de données, tandis que 2 requiert que seul le nombre de variables soit pris en compte pour le calcul de la complexité de l'espace, plutôt que la taille de ces variables. Si aucune de ces hypothèses n’est acceptée, il serait impossible d’obtenir à la O(n)fois une complexité temporelle et une O(1)complexité spatiale.

Explication

Whoo Boy, celui-ci a mis un temps long à imaginer un peu de puissance cérébrale.

Donc, aller au bonus est difficile. Nous avons besoin que les deux contrôlent une seule fois la totalité de la liste et identifient les valeurs sur lesquelles nous avons déjà effectué une itération sans complexité d'espace supplémentaire.

La manipulation de bits résout ces problèmes. Nous initialisons notre O(1)«stockage», une paire d’entiers, puis nous parcourons la liste, OU le bit indiqué dans notre premier entier et le stockage du résultat dans le second.

Par exemple, si nous 1101effectuons une opération OR avec 10, nous obtenons 1111. Si nous faisons un autre OU avec 10, nous avons toujours 1101.

Ainsi, une fois que nous avons effectué l'opération OR et que nous nous retrouvons avec le même numéro, nous avons trouvé notre duplicata. Aucun doublon dans le tableau ne provoque l'exécution du programme et une exception.

Xanderhall
la source
De plus, votre deuxième test inclut le nombre 100, mais c’est impossible, car le tableau lui-même n’est que 5 longs
SchoolBoy
En outre, cela échoue car un int n'a pas assez de stockage.
SchoolBoy
@SchoolBoy Bonne prise. Mon seul problème est qu'il ne semble pas y avoir de limite supérieure à la taille du tableau, je ne peux donc pas modifier mon code de façon réaliste pour résoudre les problèmes de mémoire.
Xanderhall
@Xanderhall C'est vrai, mais j'ai l'impression que 32 (ou si vous utilisez un nombre long, 64) est trop petit: p. Quoi qu’il en soit, imposer une limite à l’entrée, puis allouer le maximum de mémoire nécessaire et l’appeler comme mémoire O (1) n’est qu’un tricheur. C'est toujours O (n) puisque si la taille de l'entrée augmentait, la limite supérieure augmenterait de la même manière. C'est aussi pourquoi je pense qu'il est impossible de créer un algorithme O (n) O (1)
SchoolBoy
@Xanderhall PS J'approche de vos 65 ans, je suis à 67 octets: p
SchoolBoy
2

PHP, 56 44 38 32 octets

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

Courez comme ça:

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

Explication

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 octets enregistrés en utilisant des variables au lieu d'un tableau
  • Sauvegardé 6 octets en utilisant la règle "comportement indéfini" pour quand il n'y a pas de correspondance.
  • Sauvegardé 6 octets en utilisant post-incrémentation au lieu de mettre à 1 après chaque boucle

Complexité

Comme le montre la version commentée du code, la complexité temporelle est linéaire O(n). En termes de mémoire, un maximum de n+1variables sera attribué. Donc c'est ça O(n).

aross
la source
Merci de ne pas utiliser un encodage étrange. Mais vous devriez ajouter l' error_reportingoption au nombre d'octets (ou utiliser -n, qui est gratuit).
Titus
Nous avons été ici avant. Les notifications et les avertissements PHP sont ignorables. Je pourrais aussi bien les diriger /dev/null, ce qui est la même chose.
aross
J'ai tendance à me souvenir des mauvais commentaires. :) N'est-ce pas O (n)?
Titus
Oui c'est linéaire
aross
Comment est-ce O(1)pour plus d'espace? Vous attribuez littéralement une nouvelle variable par n, qui estO(n)
Xanderhall
2

Java 8, 82 78 76 octets N'est plus viable, 75 67 64 octets ci-dessous en modification

En tant que fonction lambda:

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

Peut être probablement beaucoup plus petit, c'était très rapide.

Explication:

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
}

*Modifier*

75 67 64 octets utilisant la stratégie de négation:

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

Essayez-le en ligne!

(-3 octets grâce à @Nevay)

Explication:

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
}

Boucle sur le tableau, nier pour garder une trace. S'il n'y a pas de dupes, il suffit de lancer une erreur.

Tous deux travaillent sur la complexité en temps O (n) et en espace O (n).

Écolier
la source
Il est à noter que cela devra être attribué à un retour lambda Number, car iest un longet -1est un int.
Jakob
@Jakob Non nécessaire, -1 étant un int, sera automatiquement converti en un long sans spécifier explicitement le casting
SchoolBoy
Il lancera implicitement long, mais pas Longcomme il se doit, pour que le lambda soit attribué à un Function. L'avez-vous testé? Quoi qu'il en soit, cette solution peut être remplacée par votre nouvelle.
Jakob
Vous pouvez utiliser des types bruts Set s=new HashSet();pour économiser 7 octets. (De plus, l'importation java.util.*;doit toujours être incluse dans le nombre d'octets -> +19 octets.) L'instruction return peut être return++j, l'instruction if peut être supprimée a->{int i=0,j;for(;(a[j=Math.abs(a[i++])-1]*=-1)<0;);return++j;}(-3 octets).
Nevay
2

Brachylog , 5 octets

a⊇=bh

Essayez-le en ligne!

Explication

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.

Le préfixe intégré à Adfix arépertorie d'abord tous les préfixes par ordre croissant de longueur, puis les suffixes par ordre décroissant. Ainsi, la sortie est produite par le préfixe le plus court qui le permet, le cas échéant. Si un préfixe n'a pas de doublons, le reste du programme échoue car chaque sous-séquence d'éléments égaux a une longueur de 1 et le premier élément de sa queue n'existe pas. Si un préfixe a un élément répété, nous pouvons choisir la sous-séquence de longueur 2 contenant les deux, et le programme renvoie la dernière.

Zgarb
la source
Une autre solution de 5 octets:, a⊇Ċ=hqui ne porte que sur une longueur de 2 sous-ensembles.
Fataliser
1

C #, 145 octets

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

Probablement un moyen beaucoup plus court de faire cela en C # avec une simple boucle mais je voulais l'essayer avec Linq.

Essayez-le en ligne!

Version complète / formatée:

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();
        }
    }
}
TheLethalCoder
la source
Voici la version en boucle simple. Mais j'aime beaucoup plus la version Linq.
LiefdeWen
@LiefdeWen Postez-le comme une réponse :) Bien que j'aime généralement mieux Linq aussi :) Je pourrais peut-être le faire plus court avec Linq aussi, mais je suis maintenant sûr.
TheLethalCoder
Nah, cette question est surpeuplée et je préférerais que vous obteniez les votes positifs pour cette question.
LiefdeWen
1

Haskell , 78 69 octets

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

Essayez-le en ligne!

9 octets sauvés grâce à @nimi

Un chemin de base à travers la liste. Si l'élément actuel n'a pas encore été vu ( i<0) et qu'il est dans la liste d'accumulateur ( elem x a), stockez l'index actuel. Sinon, gardez l'index -1. Dans tous les cas, ajoutez l'élément en cours à la liste des accumulateurs.

EDIT : Je n’ai pas lu la question suffisamment attentivement: ce code affiche l’index du deuxième élément d’un élément dupliqué.

jferard
la source
Vous pouvez utiliser le « Shorter conditionnelle » de nos « Conseils pour jouer au golf dans Haskell » : \ ... ->(last$i:[j|i<0,elem x a],x:a). Aussi: pas besoin de la f=, car les fonctions sans nom sont autorisées.
nimi
@nimi merci pour le tuyau!
jferard
1

Python 2, 71 65 octets

Renvoie Nones'il n'y a pas d'élément en double

Edit: -6 octets grâce à @ musicman523

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

Essayez-le en ligne!

O (n) complexité temporelle, O (n) complexité spatiale, O (1) espace auxiliaire.

Comme la liste d’entrée utilise O (n) espace, la complexité de l’espace est liée à cela. Ce qui signifie que nous ne pouvons pas avoir une complexité d'espace inférieure à O (n)

Modifie la liste d'origine. Si ce n'est pas autorisé, nous pourrions le faire avec la même complexité avec 129 octets.

Explication

Étant donné que chaque élément est supérieur à 0 et inférieur ou égal à la taille de la liste, la liste a pour chaque élément a, un élément d'indice a - 1 (0 indexé). Nous exploitons cela en disant que si l'élément d'indice i est négatif, nous l'avons déjà vu.

Pour chaque élément a de la liste n, on laisse u négatif la valeur absolue de a. (Nous le laissons négatif car python peut indexer des listes avec des index négatifs, sinon nous aurions besoin de le faire u=abs(a)-1 ) Si l'élément à l'index u dans la liste est négatif, nous l'avons déjà vu et pouvons donc renvoyer -u (pour obtenir le valeur absolue de a, car tous les éléments sont positifs) . Sinon, nous définissons l'élément à l'index u comme négatif, pour nous rappeler que nous avons déjà vu un élément de valeur a.

Halvard Hummel
la source
Bon travail! 65 octets
musicman523
Êtes-vous sûr que c'est O (1) en mémoire? Vous utilisez toujours n bits de mémoire pour stocker les numéros déjà visités, même s'ils se trouvent dans le signe. Il me semble que c'est un O (n) déguisé
Wheat Wizard
Techniquement, cela utilise O (n) espace - les n bits de signe. Si le tableau ne peut contenir que des valeurs entre 1et n, comme c'est le cas, alors cela ne fonctionne évidemment pas.
Oliver Ni
Cela revient vraiment à la représentation que vous choisissez pour les chiffres. Si des nombres non signés sont utilisés, il s'agit alors de l' espace auxiliaire O (n) . Si des nombres signés sont utilisés, alors le bit de signe est déjà là, ce qui signifie O (1) espace auxiliaire.
Halvard Hummel
Je suis d'accord avec toi. Personnellement , je vous laisser glisser à l' aide des entiers signés tant que vous ne l' avez pas utilisé le bit de signe, il devrait être sur l'algorithme non les aspects techniques du système. Cela étant dit, je pense que si vous voulez utiliser les bits de signe, vous devez les compter. Je pense que cette réponse est assez intelligente. S'il me restait des votes aujourd'hui, je voterais à nouveau pour contrebalancer le vote négatif.
Wheat Wizard