Найти дубликаты в массиве с эффективным использованием памяти
A это массив целых чисел.
Все значения между 0 в A.Length-1
это значит 0 <= A[i] <= A.Length-1
Я должен найти повторяющиеся элементы; и если есть несколько повторяющихся элементов, то выберите тот, который имеет меньший индекс для повторяющегося элемента.
например:
a = [3, 4, 2, 5, 2, 3]
затем
result = 2
Это был вопрос для интервью. Я использовал другой массив для хранения элементов и проверки, когда он повторяется. Тогда это дало мне тайм-аут для некоторых тестовых случаев. Интервьюер посоветовал зацикливать массив только один раз и не создавать никакой дополнительной структуры данных.
4 ответа
Нет необходимости в другой структуре данных. Вы можете использовать сам вход как хэш-сет.
Каждый раз, когда вы видите значение, добавляйте 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], все элементы без знака или я могу использовать отрицательные числа, если хочу? - так далее.
Во время интервью я не стал бы утверждать, что это идеальный ответ, вместо этого я бы обсудил эти предположения с интервьюером и скорректировал его. Например, другой ответ предложил использовать отрицательные числа, но возможно, что тип данных элементов - беззнаковый тип и т. Д.
Предполагается, что собеседование вызовет техническую дискуссию, чтобы изучить ваши знания и креативность.
Примечание: решение не будет выполнено, если есть элемент со значением ноль. Решение Оливье может справиться с такими случаями.
Делаем элемент с индексом 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])];
}
Я хотел бы уточнить решение @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);
удовлетворить все требования.
Для тех, кто хочет реализовать проблему, я предлагаю два варианта (в 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]));
}
}