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

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

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

Меня интересует вторая часть , т. Е. Без использования вспомогательного хранилища . Есть ли у вас какие-либо идеи?

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

Например:

Input: 1,2,3,2,4 => 12 Expected: 1,2,3,4 => 10 Input - Expected => 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 операции.

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

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

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

Помимо этого, однако, вот деструктивный алгоритм, который может безопасно масштабироваться для любого 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 играет никакой роли в 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 :)

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

Добавьте все числа вместе. Конечная сумма будет 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 равна (1000 * 1001) / 2. Разница с тем, что вы получаете, это ваш номер.

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

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

 sum = 0
 для каждого элемента массива:
    sum + = этот элемент массива
 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 ..

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

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

 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), основанного на представлении базы 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, если решить это уравнение.

  • Количество экземпляров Java в каждом массиве в массиве
  • Java Удалить дубликаты из массива?
  • Как суммировать все значения столбцов в многомерном массиве?
  • Почему cout печатает массивы char по-разному от других массивов?
  • Исключение Java ArrayIndexOutOfBounds
  • Самый быстрый способ найти недостающее число в массиве чисел
  • Подключить 4 проверить для алгоритма выигрыша
  • найти элемент в отсортированной матрице
  • Как инициализировать массив байтов в Java?
  • Инициализация массива объектов без конструктора по умолчанию
  • Как сортировать на месте с помощью алгоритма сортировки слияния?
  • Interesting Posts

    Скрытие дубликатов панелей инструментов Элементы в Eclipse

    Воспроизвести сигнал оповещения (то же, что и мелодия вызова по умолчанию)

    Как использовать Google Analytics с помощью Phonegap без плагина?

    Преобразование AutoMapper из нескольких источников

    Как создать пользовательский тег Facelets?

    Как скопировать файлы из папки «assets» на SDCard?

    Как добавить два числа без использования ++ или + или другого арифметического оператора

    HTTP и HTTPS iframe

    Maven 3.3.1 ECLIPSE: -Dmaven.multiModuleProjectDirectory система не задана

    В чем разница между прошивкой и программным обеспечением / ОС?

    Является ли main () действительно началом программы на C ++?

    как я могу получить одну и ту же страницу с помощью кнопки «Назад» браузера

    Обновление Java PriorityQueue, когда его элементы меняют приоритет

    Различать один клик и двойной щелчок в Java

    Обновление для Windows 10 не работает (0x80080005), и служба обновления Windows не запускается (0x80070002)

    Давайте будем гением компьютера.