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

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

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

это можно сделать, используя XOR оператора.

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

теперь делать XOR всех элементов и всех индексов. Мы получаем 2, который является дублирующим элементом. Это происходит потому, что, 0 не играет никакой роли в операции. Остальные 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 решение :)

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

сложить все числа вместе. Итоговая сумма будет 1+2+...+1000+дублирующий номер.

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

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

решение:

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, так как здесь оно произвольно).

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

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

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

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

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

объяснение, почему он работает в @Matthieu M.'s answer.

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

public static void main(String[] args) {
    int start = 1;
    int end = 10;
    int arr[] = {1, 2, 3, 4, 4, 5, 6, 7, 8, 9, 10};
    System.out.println(findDuplicate(arr, start, end));
}

static int findDuplicate(int arr[], int start, int end) {

    int sumAll = 0;
    for(int i = start; i <= end; i++) {
        sumAll += i;
    }
    System.out.println(sumAll);
    int sumArrElem = 0;
    for(int e : arr) {
        sumArrElem += e;
    }
    System.out.println(sumArrElem);
    return sumArrElem - sumAll;
}

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

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

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

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

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

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

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

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

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

   for i=0 to n-1
        begin:  
              diff = a[i]-i;
              dup = dup + diff;
        end
   // where dup is the duplicate element..

но с помощью этого метода я не смогу узнать индекс, в котором присутствует дубликат элемента!

для этого мне нужно пройти массив другое время, которое не желательно.

улучшение ответа Fraci на основе свойства XORing последовательных значений:

int result = xor_sum(N);
for (i = 0; i < N+1; i++)
{
   result = result ^ array[i];
}

где:

// Compute (((1 xor 2) xor 3) .. xor value)
int xor_sum(int value)
{
    int modulo = x % 4;
    if (modulo == 0)
        return value;
    else if (modulo == 1)
        return 1;
    else if (modulo == 2)
        return i + 1;
    else
        return 0;
}

или в псевдокоде / математическом языке F (n), определяемом как (оптимизированный):

if n mod 4 = 0 then X = n
if n mod 4 = 1 then X = 1
if n mod 4 = 2 then X = n+1
if n mod 4 = 3 then X = 0

и в канонической форме f(n) является:

f(0) = 0
f(n) = f(n-1) xor n

мой ответ на вопрос 2:

найти сумму и произведение чисел от 1 - (до) N, скажем SUM,PROD.

найти сумму и произведение чисел из 1-N-x-y, (предположим, что x, Y отсутствует), скажем mySum, myProd,

таким образом:

SUM = mySum + x + y;
PROD = myProd* x*y;

таким образом:

x*y = PROD/myProd; x+y = SUM - mySum;

мы можем найти x, y, если решить это уравнение.