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

Question

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

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

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

Answer 1

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

Answer 2

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

Answer 3

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

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

Answer 4

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

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

Answer 5

В aux-версии вы сначала устанавливаете все значения на -1 и, повторяя, проверяете, вставили ли вы уже значение в массив aux. Если нет (значение должно быть -1, то), вставьте. Если у вас есть дубликат, вот ваше решение!

В случае без aux вы извлекаете элемент из списка и проверяете, содержит ли это значение остальная часть списка. Если он есть, то вы его нашли.

private static int findDuplicated(int[] array) {
    if (array == null || array.length < 2) {
        System.out.println("invalid");
        return -1;
    }
    int[] checker = new int[array.length];
    Arrays.fill(checker, -1);
    for (int i = 0; i < array.length; i++) {
        int value = array[i];
        int checked = checker[value];
        if (checked == -1) {
            checker[value] = value;
        } else {
            return value;
        }
    }
    return -1;
}

private static int findDuplicatedWithoutAux(int[] array) {
    if (array == null || array.length < 2) {
        System.out.println("invalid");
        return -1;
    }
    for (int i = 0; i < array.length; i++) {
        int value = array[i];
        for (int j = i + 1; j < array.length; j++) {
            int toCompare = array[j];
            if (value == toCompare) {
                return array[i];
            }
        }
    }
    return -1;
}

Answer 6

Мой ответ на вопрос 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, если решим это уравнение.

Answer 7

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

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

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

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

Answer 8

Улучшение ответа Фраки на основе свойства последовательных значений XOR:

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

Answer 9

Треугольное число 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