Найти дубликат в массиве с эффективным использованием памяти

Ответ 1

Нет необходимости в другой структуре данных. Вы можете использовать сам вход как хэш.

Каждый раз, когда вы видите значение, добавьте A.Length к элементу, соответствующему этому индексу. Поскольку значения, возможно, уже были увеличены, вы должны посмотреть на значение как A[i] mod A.length.

Если вы найдете элемент уже> = A.length.. у вас есть повторение. (Помните, что проблема заключается в том, что все элементы находятся в интервале [0, A.Length-1])

Отслеживайте самый низкий индекс, который был найден как повторяющийся.

Это приводит к сложности O (N) (один проход) и не использует дополнительную структуру данных, то есть размер O (1)

Ключевой концепцией этого подхода является то, что хешеты работают таким образом. Понятно, что это косвенно связано с принципом голубины. https://en.wikipedia.org/wiki/Pigeonhole_principle

Примечание. Во время собеседования было бы важно задать конкретные вопросы реализации, обсудить ограничения, допущения и т. Д.: - Каков тип данных элементов в списке? - если значения находятся в диапазоне [0..A.length-1], все элементы без знака или я могу использовать отрицательные числа, если бы захотел? - так далее.

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

Предполагается, что собеседование начнет техническую дискуссию для изучения ваших знаний и творчества.

Ответ 2

Примечание. Решение выходит из строя, если есть элемент со значением нуля. Решение Olivier может обрабатывать такие случаи.

Создание элемента с индексом A [i] отрицательным. Он проходит один цикл только один раз.

for(int i=0; i<A.Length; i++)
    {
        if (A[Math.Abs(A[i])] < 0){ return Math.Abs(A[i]);}
        A[Math.Abs(A[i])] = -A[Math.Abs(A[i])];
    }

Ответ 3

Я хотел бы уточнить решение @AryanFirouzian и вернуть все дубликаты, используя yield return. Кроме того, использование переменной temp упрощает код.

public static IEnumerable<int> FindDuplicates(int[] A)
{
    for (int i = 0; i < A.Length; i++) {
        int absAi = Math.Abs(A[i]);
        if (A[absAi] < 0) {
            yield return absAi;
        } else {
            A[absAi] *= -1;
        }
    }
}

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

Лучшее решение устраняет повторяющиеся результаты, но все же возвращает второй индекс и имеет проблему с 0 значениями. Он также возвращает сам индекс, чтобы продемонстрировать неправильную проблему индекса

public static IEnumerable<(int index, int value)> FindDuplicates(int[] A)
{
    for (int i = 0; i < A.Length; i++) {
        int x = A[i] % A.Length;
        if (A[x] / A.Length == 1) {
            yield return (i, x);
        }
        A[x] += A.Length;
    }
}

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

var A = new int[] { 3, 4, 2, 5, 2, 3, 3 };
foreach (var item in FindDuplicates(A)) {
    Console.WriteLine($"[{item.index}] = {item.value}");
}

Он возвращает

[4] = 2
[5] = 3

Мое окончательное решение, которое устраняет все эти проблемы (по крайней мере, я надеюсь): он кодирует первый индекс, добавляя (i + 1) * A.Length к первому вхождению значения. (i + 1) так как i может быть 0. Затем индекс можно декодировать с помощью обратной операции (A[x]/A.Length) - 1.

Затем, поскольку мы хотим вернуть результат только по первому повторяющемуся значению, мы устанавливаем значение отрицательным значением, чтобы исключить его из дальнейшей обработки. Впоследствии исходное значение может быть получено с помощью Math.Abs(A[i]) % A.Length.

public static IEnumerable<(int index, int value)> FindDuplicates(int[] A)
{
    for (int i = 0; i < A.Length; i++) {
        int x = Math.Abs(A[i]) % A.Length;
        if (A[x] >= 0) {
            if (A[x] < A.Length) { // First occurrence.
                A[x] += (i + 1) * A.Length; // Encode the first index.
            } else { // Second occurrence.
                int firstIndex = (A[x] / A.Length) - 1; // Decode the first index.
                yield return (firstIndex, x);

                // Mark the value as handeled by making it negative;
                A[x] *= -1; // A[x] is always >= A.Length, so no zero problem.
            }
        }
    }
}

Возвращает ожидаемый результат

[2] = 2
[0] = 3

Наши элементы - это ints, которые не имеют идентичности. Т.е. мы можем вернуть один из дубликатов в любом индексе, так как нельзя различить два одинаковых int. В случае, если элементы имеют идентификатор (они могут быть ссылочными типами с равными значениями, но с разными ссылками или иметь дополнительные поля, не участвующие в тестировании равенства), мы должны были бы вернуть первое вхождение с

yield return (firstIndex, Math.Abs(A[firstIndex]) % A.Length);

для удовлетворения всех требований.

Ответ 4

Для тех, кто хочет реализовать проблему, я предлагаю два варианта (в С#, как в тегах), один с использованием принятого ответа и один с использованием aproach другого ответа, используя противоположность элементов. Однако последнее решение имеет проблему с нулевым значением и требует некоторого трюка.

Первое решение

using System;
public class Program
{
    public static void Main()
    {
        int[] a = {3, 4, 0, 5, 2, 3};
        int N = 6;
        int min_index = 0; 
        bool found = false;
        int index = -1;
        int i = 0;
        while(i < N && !found)
        {

            if(a[i] >= N) 
                index = a[i] % N;
            else
                index = a[i];

            if(a[index] >= N) //its a duplicated elements 
            {
                min_index = i;
                found = true;
            }else
            {
                a[index] += N;
            }
            i++;

        }

        Console.WriteLine("Result = " + a[min_index] % N);
    }
}

Второе решение

    using System;
public class Program
{
    public static void Main()
    {
        int[] a = {3, 4, 2, 5, 2, 3};
        int N = 6;
        int min_index = N-1; 
        bool found = false;
        int index = -1;
        int i = 0;
        while(i < N && !found)
        {
            if(a[i] == -N+1) //it was 0
                index = 0;
            else
                index = Math.Abs(a[i]);

            if(a[index] < 0 || a[index] == -N+1) //its a duplicated elements 
            {
                min_index = i;
                found = true;
            }else
            {
                if(a[index] > 0)
                {
                    a[index] = -a[index];
                }else
                {
                    a[index] += -N+1;
                }
            }
            i++;
        }

        if(a[min_index] == -N+1)
            a[min_index] = 0;

        Console.WriteLine("Result = " + Math.Abs(a[min_index]));
    }
}