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

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

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

Решение:

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

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

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

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

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

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

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

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

Сложите все числа вместе. Окончательная сумма будет равна 1 + 2 + ... + 1000 + повторяющееся число.

Считаются ли аргументы и стеки вызовов вспомогательной памятью?

int sumRemaining(int* remaining, int count) {
    if (!count) {
        return 0;
    }
    return remaining[0] + sumRemaining(remaining + 1, count - 1);
}

printf("duplicate is %d", sumRemaining(array, 1001) - 500500);

Изменить: версия хвостового вызова

int sumRemaining(int* remaining, int count, int sumSoFar) {
    if (!count) {
        return sumSoFar;
    }
    return sumRemaining(remaining + 1, count - 1, sumSoFar + remaining[0]);
}
printf("duplicate is %d", sumRemaining(array, 1001, 0) - 500500);

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

Это можно сделать с помощью оператора 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 :)

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

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

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

Объяснение того, почему оно работает, можно найти в ответе @Matthieu M. .

Обновление 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

Нет необходимости в дополнительном хранилище (кроме переменной цикла).

int length = (sizeof array) / (sizeof array[0]);
for(int i = 1; i < length; i++) {
   array[0] += array[i];
}

printf(
    "Answer : %d\n",
    ( array[0] - (length * (length + 1)) / 2 )
);

Что ж, есть очень простой способ сделать это ... каждое из чисел от 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

Треугольник с числом T (n) - это сумма n натуральных чисел от 1 до n. Его можно представить как n (n + 1) / 2. Таким образом, зная, что среди заданных 1001 натурального числа дублируется одно и только одно число, вы можете легко просуммировать все заданные числа и вычесть T (1000). Результат будет содержать этот дубликат.

Для треугольного числа T (n), если n является любой степенью 10, существует также прекрасный метод нахождения этого T (n) на основе представления по основанию 10:

n = 1000
s = sum(GivenList)
r = str(n/2)
duplicate = int( r + r ) - s