Учитывая массив a, который содержит только числа в диапазоне от 1 до a.length, найдите первый дубликат числа, для которого второе вхождение имеет минимальный индекс. Другими словами, если имеется более 1 дублированного числа, вернуть номер, для которого второе вхождение имеет меньший индекс, чем второе вхождение другого числа. Если таких элементов нет, ваша программа / функция может привести к неопределенному поведению.

Пример:

Для a = [2, 3, 3, 1, 5, 2], выход должен быть firstDuplicate(a) = 3.

Есть 2 дубликата: номера 2 и 3. Второе вхождение 3 имеет меньший индекс, чем второе вхождение 2, поэтому ответ 3.

Для a = [2, 4, 3, 5, 1], выход должен быть firstDuplicate(a) = -1.

Это код-гольф , поэтому выигрывает самый короткий ответ в байтах.

БОНУС: Можете ли вы решить это за O (n) сложность времени и O (1) дополнительную сложность пространства?

Python 2 , 34 байта

O (n ² ) время, O (n) пространство

^{Благодаря @vaultah сохранено 3 байта, а еще @xnor!}

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

Попробуйте онлайн!

JavaScript (ES6), 47 36 31 25 байт

Сохранено 6 байтов благодаря ThePirateBay

Возвращает, undefinedесли решения не существует.

Сложность времени: O (n) :-)
Сложность пространства: O (n) :-(

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

Как?

Мы отслеживаем уже встречающиеся значения, сохраняя их как новые свойства исходного массива a , используя отрицательные числа. Таким образом, они не могут мешать оригинальным записям.

демонстрация

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 байта

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

Возможность сопоставления с образцом Mathematica - это круто!

Возвращает оригинал Listдля неверного ввода.

объяснение

#/.

На входе заменить ...

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

A Listс дублирующим элементом, с 0 или более элементами до, между и после дубликатов ...

... :>a

С дублирующим элементом.

Желе , 5 байт

Ṛœ-QṪ

Попробуйте онлайн!

Как это работает

Ṛœ-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 байт

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

Попробуйте онлайн! Сбои, если дубликат не найден.

Желе , 6 байт

xŒQ¬$Ḣ

Попробуйте онлайн!

Возвращает первый дубликат или 0, если дубликатов нет.

объяснение

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 байт

æ@bX ¦Y

Проверьте это онлайн!

объяснение

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

В качестве альтернативы:

æ@¯Y øX

Проверьте это онлайн!

объяснение

 æ@   ¯ 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 байт

h.-Q{

Тестирование

Удалите из Q первое появление каждого элемента в Q, затем верните первый элемент.

Dyalog APL, 27 24 20 19 13 12 11 байт

⊢⊃⍨0⍳⍨⊢=⍴↑∪

Теперь модифицировано, чтобы не зависеть от v16! Попробуйте онлайн!

Как? (С вводом N )

• ⊢⊃⍨...- N по этому показателю:
  • ⍴↑∪- N с удаленными дубликатами, с правой стороны, 0чтобы соответствовать N
  • ⊢=- Элементарное равенство с N
  • 0⍳⍨- указатель первый 0. `

Python 3 , 94 92 байта

O (n) время и O (1) дополнительная память.

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

Попробуйте онлайн!

Источник алгоритма .

объяснение

Основная идея алгоритма состоит в том, чтобы проходить через каждый элемент слева направо, отслеживать появившиеся числа и возвращать число при достижении числа, которое уже появилось, и возвращать -1 после прохождения каждого элемента.

Однако он использует умный способ хранения появившихся чисел без использования дополнительной памяти: хранить их как знак элемента, индексированного по номеру. Например, я могу представить тот факт, что 2и 3уже появился, имея a[2]и a[3]отрицательный, если массив 1-индексирован.

Perl 6 , 13 байт

*.repeated[0]

Попытайся

объяснение

• Он *находится в терминах Term, поэтому весь оператор - это лямбда- выражение Wh whatCode.

• Это .repeatedметод, который приводит к каждому значению, за исключением первого раза, когда каждое значение было просмотрено.

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

• [0]просто возвращает первое значение в Seq .
  Если значение отсутствует, возвращается ноль .
  ( Nil является основой типов Failure , и все типы имеют свое собственное неопределенное значение, поэтому Nil отличается от неопределенного значения в большинстве других языков)

Обратите внимание, что поскольку реализация.repeated генерирует Seq, это означает, что он не начинает выполнять какую-либо работу до тех пор, пока вы не запросите значение, и он только выполняет работу, достаточную для генерации того, что вы запрашиваете.
Таким образом, было бы легко утверждать, что это имеет в худшем случае O (n)  временную сложность и в лучшем случае O (2)  временную сложность, если второе значение является повторением первого.
Подобное можно, вероятно, сказать о сложности памяти.

APL (Dyalog) , 20 байтов

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

Попробуйте онлайн!

2⍴¯1 отрицательный г eshaped в длину-два списка

⎕, получить ввод (мнемоника: консоль) и предварять это

n← хранить это в н

,\ префиксы n (лит. кумулятивная конкатенация)

(… )¨ Применить следующую молчаливую функцию к каждому префиксу

 , [is] ravel (просто гарантирует, что префикс является списком)

 ≢ отличается от

 ∪ уникальные элементы [?] (т.е. есть ли у префикса дубликаты?)

n/⍨ используйте это, чтобы отфильтровать n (удаляет все элементы до тех пор, пока не будет найден первый, для которого была найдена копия)

⊃ выбрать первый элемент из этого

APL (Дьялог) , 11 байт

Согласно новым правилам , выдает ошибку, если дубликатов не существует.

⊢⊃⍨⍬⍴⍳∘≢~⍳⍨

Попробуйте онлайн!

⍳⍨ показатели первого появления каждого элемента

~ удалено из

⍳∘≢ из всех показателей

⍬⍴ изменить это в скаляр (дает ноль, если нет данных)

⊃⍨ использовать это, чтобы выбрать из (дает ошибку на нуле)

⊢ Аргумент

APL, 15

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

Похоже, мы можем вернуть 0 вместо -1, если нет дубликатов (спасибо Adám за комментарий). Так что на 3 байта меньше.

Немного описания:

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

Для справки, старое решение добавило -1 к списку в конце, поэтому, если список окажется пустым, он будет содержать -1, а первый элемент будет -1.

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

Попробуйте это на tryapl.org

Сетчатка , 26 24 байта

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

Попробуйте онлайн! Объяснение: \b(\d+)\bсопоставляет каждое число по очереди, а затем просмотрщик смотрит, является ли число дубликатом; если это 1совпадение, !выводится результат, а не количество совпадений. К сожалению, размещение внешнего вида вначале не работает, иначе это сэкономит несколько байтов. Редактировать: Добавлено 7 байт для соответствия -1возвращаемому значению при отсутствии совпадения. Сохранено 2 байта благодаря @MartinEnder.

MATL , 8 байт

&=Rsqf1)

Выдает ошибку (без вывода), если дубликатов не существует.

Попробуйте в MATL Online!

объяснение

&=   % 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 байта

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

Вырежьте несколько символов из ответа @djhurio, но у вас недостаточно репутации, чтобы комментировать.

J, 17 16 байт

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

Как?

(*/{_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 байт

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

Попробуйте онлайн!

J , 12 байт

,&_1{~~:i.0:

Попробуйте онлайн!

объяснение

,&_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 символов

Работает только в ⎕IO←0.

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

Удалите из списка индексов элементов аргумента с добавленным «-1» список индексов своего куска, а затем выберите первое из того, что осталось. Если после удаления остается только пустой вектор, его первый элемент по определению 0, который используется для индексации расширенного аргумента, производящего желаемый -1.

Рубин , 28 36 байт

В первый раз неправильно понял вызов. O(n)время, O(n)пространство.

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

Попробуйте онлайн!

Java (OpenJDK 8) , 65 117 109 байт

Предыдущее 65-байтовое решение:

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

Новое решение 19 байтов включены дляimport java.math.*;

-8 байт благодаря @Nevay

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

Попробуйте онлайн!

редактировать

Алгоритм в моей исходной программе был в порядке, но статический размер используемого типа данных означал, что он сломался довольно быстро, как только размер превысил определенный порог.

Я изменил тип данных, используемый в вычислениях, чтобы увеличить лимит памяти программы, чтобы приспособиться к этому (используя BigIntegerдля произвольной точности вместо intили long). Однако, это делает спорным, считается ли это O(1)сложностью пространства.

Я оставлю свое объяснение ниже без изменений, но я хочу добавить, что теперь я считаю, что невозможно достичь O(1)космической сложности без некоторых предположений.

доказательство

Определите Nкак целое число такое, что 2 <= N.

Позвольте Sбыть список, представляющий ряд случайных целых чисел [x{1}, ..., x{N}], где x{i}имеет ограничение 1 <= x{i} <= N.

Сложность по времени (в обозначениях Big-O), необходимая для итерации по этому списку ровно один раз для каждого элемента, равна O(n)

Задача состоит в том, чтобы найти первое дублированное значение в списке. Более конкретно, мы ищем первое значение, Sкоторое является дубликатом предыдущего элемента в списке.

Позвольте pи qбыть позиции двух элементов в списке, что p < qи x{p} == x{q}. Наша задача - найти самое маленькое q, удовлетворяющее этим условиям.

Очевидный подход к этой проблеме - перебрать S и проверить, x{i}существует ли наш объект в другом списке T: если x{i}его нет в T, мы сохраняем его в T. Если x{i}существует в T, это первое дублирующее значение и, следовательно, наименьшее q, и как таковое мы возвращаем его. Эта космическая эффективность есть O(n).

Чтобы достичь O(1)пространственной сложности при сохранении O(n)временной сложности, мы должны хранить уникальную информацию о каждом объекте в списке в ограниченном количестве пространства. Из-за этого единственный способ, которым любой алгоритм мог работать вO(1)Сложность пространства заключается в том, что: 1. N задана верхняя граница, соответствующая памяти, необходимой для хранения максимального количества возможных значений для конкретного конечного типа данных. 2. Переназначение одной неизменяемой переменной не учитывается в зависимости от сложности, а только от количества переменных (список состоит из нескольких переменных). 3. (Основано на других ответах) Список (или, по крайней мере, элементы списка) изменчив, а тип данных списка предварительно задан как целое число со знаком, что позволяет вносить изменения в элементы, находящиеся далее в списке. без использования дополнительной памяти.

1 и 3 требуют предположений и спецификаций о типе данных, в то время как 2 требует, чтобы при расчете сложности пространства учитывалось только количество переменных, а не их размер. Если ни одно из этих допущений не будет принято, было бы невозможно достичь как O(n)временной, так и O(1)пространственной сложности.

объяснение

Черт возьми, этот занял смущающе много времени, чтобы придумать немного умственных способностей.

Итак, идти за бонусом сложно. Нам нужно одновременно работать со всем списком ровно один раз и отслеживать, какие значения мы уже перебрали, без дополнительной сложности с пространством.

Битовая манипуляция решает эти проблемы. Мы инициализируем наше O(1)«хранилище», пару целых чисел, затем выполняем итерацию по списку, ИЛИ вставляем i-й бит в наше первое целое число и сохраняем этот результат во втором.

Например, если у нас есть 1101, и мы выполняем операцию ИЛИ 10, мы получаем 1111. Если мы сделаем еще одно ИЛИ с нами 10, у нас все еще будет 1101.

Поэтому, как только мы выполним операцию ИЛИ и получим тот же номер, мы нашли наш дубликат. Отсутствие дубликатов в массиве приводит к тому, что программа запускается и выдает исключение.

PHP, 56 44 38 32 байта

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

Запустите так:

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

объяснение

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 байт с использованием переменных вместо массива
• Сохранено 6 байтов за счет использования правила «неопределенное поведение» в случае отсутствия совпадения.
• Сохранено 6 байтов с использованием постинкремента вместо установки в 1 после каждого цикла

сложность

Как видно из закомментированной версии кода, временная сложность линейна O(n). С точки зрения памяти, максимум n+1переменных будет назначен. Так вот O(n).

Java 8, 82 78 76 байтов Больше не жизнеспособен, 75 67 64 байтов ниже в редактировании

В качестве лямбда-функции:

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

Вероятно, можно сделать намного меньше, это было очень быстро.

Объяснение:

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
}

*Редактировать*

75 67 64 байта, используя стратегию отрицания:

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

Попробуйте онлайн!

(-3 байта благодаря @Nevay)

Объяснение:

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
}

Зацикливается на массиве, отрицая, чтобы отслеживать. Если нет дупликов, просто перебегает и выдает ошибку.

Оба они работают на O (n) времени и сложности O (n) пространства.

Брахилог , 5 байт

a⊇=bh

Попробуйте онлайн!

объяснение

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.

Встроенный adfix aперечисляет сначала все префиксы в порядке возрастания длины, затем суффиксы в порядке убывания длины. Таким образом, вывод производится по кратчайшему префиксу, который позволяет, если таковой имеется. Если у префикса нет дубликатов, остальная часть программы завершается с ошибкой, поскольку каждая подпоследовательность равных элементов имеет длину 1, а первый элемент его хвоста не существует. Если у префикса есть повторяющийся элемент, мы можем выбрать подпоследовательность длины-2, содержащую оба, и программа возвращает последний.

C #, 145 байт

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

Вероятно, гораздо более короткий способ сделать это в C # с простым циклом, но я хотел попробовать это с Linq.

Попробуйте онлайн!

Полная / Отформатированная версия:

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 байтов

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

Попробуйте онлайн!

Сохранено 9 байт благодаря @nimi

Основной путь по списку. Если текущий элемент еще не был просмотрен ( i<0) и находится в списке аккумуляторов ( elem x a), сохраните текущий индекс. Остальное, держите индекс -1. В любом случае добавьте текущий элемент в список аккумуляторов.

РЕДАКТИРОВАТЬ : Я недостаточно внимательно прочитал вопрос: этот код выводит индекс второго элемента дубликата элемента.

Python 2, 71 65 байт

Возвращает, Noneесли нет повторяющегося элемента

Редактировать: -6 байт благодаря @ musicman523

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

Попробуйте онлайн!

O (n) временная сложность, O (n) пространственная сложность, O (1) вспомогательное пространство.

Поскольку входной список использует пространство O (n) , сложность пространства связана с этим. Это означает, что мы не можем иметь меньшую сложность пространства, чем O (n)

Изменяет ли исходный список, если это не разрешено, мы можем сделать это в той же сложности с 129 байтами

объяснение

Поскольку каждый элемент больше 0 и меньше или равен размеру списка, список имеет для каждого элемента a элемент с индексом a - 1 (индексированный 0). Мы используем это, говоря, что если элемент с индексом i отрицателен, мы видели это раньше.

Для каждого элемента a в списке n мы допустим, чтобы u было отрицательным по абсолютному значению a. (Мы допускаем, чтобы он был отрицательным, поскольку python может индексировать списки с отрицательными индексами, и в противном случае мы должны были бы это сделать u=abs(a)-1 ). Если элемент с индексом u в списке является отрицательным, мы видели это раньше и поэтому можем вернуть -u (чтобы получить абсолютное значение, так как все элементы являются положительными) . В противном случае мы устанавливаем элемент с индексом u как отрицательный, чтобы помнить, что мы видели элемент со значением a раньше.

Желе , 4 байта

ŒQi0

Попробуйте онлайн!

В случае, если все элементы уникальны, возвращается 0(неопределенное поведение).