Найти два повторяющихся элемента в данном массиве

Question

Вам дан массив из n + 2 элементов.Все элементы массива находятся в диапазоне от 1 до n.И все элементы встречаются один раз, кроме двух чисел, которые встречаются дважды.Найдите два повторяющихся числа.

Например, array = {4, 2, 4, 5, 2, 3, 1} и n = 5

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

traverse the list for i= 1st to n+2 elements
{
check for sign of A[abs(A[i])] ;
if positive then
   make it negative by   A[abs(A[i])]=-A[abs(A[i])];
else  // i.e., A[abs(A[i])] is negative
   this   element (ith element of list) is a repetition
}
Example: A[] = {1,1,2,3,2}
i=1 ; A[abs(A[1])] i.e,A[1] is positive ; so make it negative ;
so list now is {-1,1,2,3,2}

i=2 ; A[abs(A[2])] i.e., A[1] is negative ; so A[i] i.e., A[2] is repetition,
now list is {-1,1,2,3,2}

i=3 ; list now becomes {-1,-1,2,3,2} and A[3] is not repeated
now list becomes {-1,-1,-2,3,2}

i=4 ;
and A[4]=3 is not repeated

i=5 ; we find A[abs(A[i])] = A[2] is negative so A[i]= 2 is a repetition,

This method modifies the original array.

Как этот алгоритм дает правильные результаты, т.е. как он работает. Ребята не воспринимают это как вопрос домашней работы, как этовопрос был недавно задан в интервью Microsoft.

Answer 1

Вам дан массив из n + 2 элементов.Все элементы массива находятся в диапазоне от 1 до n.И все элементы встречаются один раз, за ​​исключением двух чисел, которые встречаются дважды

Позволяет немного изменить это и использовать только n, а не n+2, и в первой части постановки задачи она становится

Вам дан массив из n элементов.Все элементы массива находятся в диапазоне от 1 до n

Итак, теперь вы знаете, что у вас есть массив, числа в массиве начинаются с 1 и увеличиваются на единицу для каждого элемента в массиве.Таким образом, если у вас есть 10 элементов, массив будет содержать числа от 1 до 10. 5 элементов, у вас есть от 1 до 5 и т. Д.

Из этого следует, что числа, хранящиеся в массиве, могут использоваться для индексациимассив.то есть вы всегда можете сказать A[A[i]], где i <= размер A. например, <code>A={5,3,4,1,2}; print A[A[2]]

Теперь давайте добавим один повторяющийся номер.Алгоритм берет значение каждого числа в массиве и посещает этот индекс.Мы знаем, что если мы дважды посещаем один и тот же индекс, мы знаем, что нашли дубликат.
Как мы узнаем, что дважды посещаем один и тот же индекс?
Да, мы меняем знак числа в каждом посещаемом нами индексе., если знак уже изменился, мы знаем, что мы уже были здесь, следовательно, этот индекс (не значение, сохраненное в индексе) является дублирующим числом.

Вы можете достичь того же результата, сохраниввторой массив логических значений, инициализированный как false.Этот алгоритм становится

A={123412}
B={false, false, false, false}

for(i = 1; i <= 4; i++)
{
    if(B[A[i]])
       // Duplicate
    else
       B[A[i]] = true;
}

Однако в вопросе MS вы меняете знак элемента в A вместо установки логического значения в B.

Надеюсь, это поможет,

Answer 2

То, что вы делаете, использует значения массива двумя способами: у них есть номер И у них есть знак.Вы «сохраняете» тот факт, что вы видели число n в n-м месте в вашем массиве, не теряя первоначального значения в этом месте: вы просто меняете знак.начните со всех положительных моментов, и если вы обнаружите, что ваш индекс, в котором вы хотите «сохранить» тот факт, что вы видели текущее значение, уже отрицателен, то это значение уже видно.если вы видите 4 в первый раз, вы меняете знак на четвертом месте на отрицательный.Это не меняет 4-е место, потому что вы используете [abs], когда идете туда, так что не беспокойтесь.Если вы видите еще 4, вы снова проверяете 4-е место и видите, что оно отрицательное: presto: double.

Answer 3

Когда вы найдете какой-то элемент в позиции i, скажем, n, тогда вы делаете A[abs(A(i))]=A[abs(n)] отрицательным. Поэтому, если вы найдете другую позицию j, содержащую n, вы также проверите A[abs(A(j))]=A[abs(n)]. Поскольку вы находите его отрицательным, то n повторяется:)

Answer 4

Я знаю, что это не совсем ответ на ваш вопрос, но если бы мне действительно пришлось писать этот код в реальном проекте, я бы начал с алгоритма сортировки типа quicksort, а в моей функции сравнения что-то вроде

int Compare(int l, int r)
{
    if(l == r)
    {
        // duplicate; insert into duplicateNumbers array if it doesn't exist already.
        // if we found 2 dupes, quit the sort altogether
    }
    return r - l;
}

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

Answer 5

Простой, используйте Hashtable.

Для каждого элемента проверьте, существует ли он уже O (1), а если нет, добавьте его в хеш-таблицу O (1).

Когда вы найдете предмет, который уже существует ... вот и все.