Как найти повторяющийся элемент в массиве перемешанных последовательных целых чисел?

Question

Недавно я где-то сталкивался с вопросом:

Предположим, у вас есть массив из 1001 целого числа. Целые числа расположены в случайном порядке, но вы знаете, что каждое из целых чисел находится в диапазоне от 1 до 1000 (включительно). Кроме того, каждое число появляется в массиве только один раз, за ​​исключением одного числа, которое встречается дважды. Предположим, что вы можете получить доступ к каждому элементу массива только один раз. Опишите алгоритм поиска повторного числа. Если вы использовали вспомогательное хранилище в своем алгоритме, можете ли вы найти алгоритм, который не требует его?

Что мне интересно знать, так это вторая часть , т.е. без использования вспомогательного хранилища . У вас есть идеи?

Answer 1

Просто сложите их все и вычтите общее количество, которое вы ожидаете, если из этого числа будет использовано только 1001 число.

Например:

Input: 1,2,3,2,4 => 12
Expected: 1,2,3,4 => 10

Input - Expected => 2

Answer 2

Обновление 2: Некоторые люди думают, что использование XOR для поиска повторяющегося числа - это хак или трюк. На что мой официальный ответ таков: «Я не ищу дубликат числа, я ищу дубликат паттерна в массиве наборов битов. И XOR определенно подходит лучше, чем ADD, для манипулирования наборами битов». : -)

Обновление: Просто для удовольствия, прежде чем я ложусь спать, вот альтернативное решение "в одну строку", которое требует нулевого дополнительного хранилища (даже не счетчика циклов), касается каждого элемента массива только один раз, не -разрушающий и не масштабируется вообще: -)

printf("Answer : %d\n",
           array[0] ^
           array[1] ^
           array[2] ^
           // continue typing...
           array[999] ^
           array[1000] ^
           1 ^
           2 ^
           // continue typing...
           999^
           1000
      );

Обратите внимание, что компилятор фактически вычислит вторую половину этого выражения во время компиляции, поэтому «алгоритм» будет выполнен ровно за 1002 операции.

И если значения элементов массива также известны во время компиляции, компилятор оптимизирует весь оператор до константы. : -)

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

Ну, вам нужна хотя бы одна дополнительная переменная (или регистр ЦП) для хранения индекса текущего элемента при прохождении массива.

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

for (int i = 1; i < 1001; i++)
{
   array[i] = array[i] ^ array[i-1] ^ i;
}

printf("Answer : %d\n", array[1000]);

Я оставлю упражнение, чтобы выяснить, почему это работает для вас, с простой подсказкой: -):

a ^ a = 0
0 ^ a = a

Answer 3

Неразрушающий вариант решения Франциска Пенова.

Это можно сделать с помощью оператора XOR.

Допустим, у нас есть массив размером 5: 4, 3, 1, 2, 2
Которые находятся в индексе: 0, 1, 2, 3, 4

Теперь выполните XOR всех элементов и всех индексов. Мы получаем 2, который является дублирующим элементом. Это происходит потому, что 0 не играет никакой роли в XORing. Оставшиеся индексы n-1 соединяются с одинаковыми элементами n-1 в массиве, и только непарный элемент в массиве будет дубликатом.

int i;
int dupe = 0;
for(i = 0; i < N; i++) {
    dupe = dupe ^ arr[i] ^ i;
}
// dupe has the duplicate.

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

Поскольку это вопрос собеседования, лучше всего начать с решения на основе сложения, определить ограничение переполнения и затем дать решение на основе XOR :)

При этом используется дополнительная переменная, поэтому она не полностью соответствует требованиям, указанным в вопросе.

Answer 4

Добавьте все числа вместе. Конечной суммой будет дубликат 1 + 2 + ... + 1000 +.

Answer 5

Перефразируя решение Фрэнсиса Пенова.

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

Решение:

acc = 0
for i in array: acc = acc ^ i

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

acc = 0
for i in len(array): acc = acc ^ i ^ array[i]

Что в итоге и делает решение Фрэнсиса, хотя оно уничтожает весь массив (кстати, он может уничтожить только первый или последний элемент ...)

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

Это было бы сформулировано более точно, если бы им потребовалось O(1) пробел (1000 можно увидеть как N, поскольку здесь оно произвольно).

Answer 6

Добавить все номера. Сумма целых чисел 1..1000 составляет (1000 * 1001) / 2. Отличие от того, что вы получаете, это ваш номер.

Answer 7

Если вы знаете, что у нас есть точные цифры 1-1000, вы можете сложить результаты и вычесть 500500 (sum(1, 1000)) из общей суммы. Это даст повторный номер, потому что sum(array) = sum(1, 1000) + repeated number.

Answer 8

Однострочное решение в Python

arr = [1,3,2,4,2]
print reduce(lambda acc, (i, x): acc ^ i ^ x, enumerate(arr), 0)
# -> 2

Объяснение того, почему это работает, содержится в ответе @ Матье М. .

Answer 9

Ну, есть очень простой способ сделать это ... каждое из чисел от 1 до 1000 встречается ровно один раз, за ​​исключением числа, которое повторяется .... итак, сумма от 1 .... 1000 500500. Итак, алгоритм такой:

sum = 0
for each element of the array:
   sum += that element of the array
number_that_occurred_twice = sum - 500500

Answer 10

public int duplicateNumber(int[] A) {
    int count = 0;
    for(int k = 0; k < A.Length; k++)
        count += A[k];
    return count - (A.Length * (A.Length - 1) >> 1);
}