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

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

0 голосов
/ 29 августа 2018

A - массив целых чисел.

Все значения находятся в диапазоне от 0 до A.Length-1

это значит 0 <= A[i] <= A.Length-1

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

например: 

a = [3, 4, 2, 5, 2, 3]

тогда 

result = 2

Это был вопрос для интервью. Я использовал другой массив для хранения элементов и проверки, когда он повторяется. Тогда это дало мне тайм-аут для некоторых тестовых случаев. Интервьюер посоветовал зацикливать массив только один раз и не создавать никакой дополнительной структуры данных.

Ответы [ 4 ]

0 голосов
/ 30 августа 2018

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

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

Однако это решение не возвращает элемент с более низким индексом и, если существует более 2 одинаковых копий, оно будет возвращать одно и то же значение более одного раза. Другая проблема заключается в том, что 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

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

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

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

0 голосов
/ 29 августа 2018

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

Создание элемента с индексом 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])];
    }
0 голосов
/ 29 августа 2018

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

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

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]));
    }
}
0 голосов
/ 29 августа 2018

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

Каждый раз, когда вы видите значение, добавьте 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], все элементы не подписаны или я могу использовать отрицательные числа, если я хочу? - и т. д.

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

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

...