Обнаружение дублирующего элемента в массиве

Существует массив размера n, а элементы, содержащиеся в массиве, находятся между 1 и n-1, так что каждый элемент возникает один раз, и только один элемент встречается более одного раза. Нам нужно найти этот элемент.

Хотя это очень часто задаваемые вопросы, я до сих пор не нашел правильного ответа. Большинство предложений заключается в том, что я должен добавить все элементы в массиве, а затем вычесть из него сумму всех индексов, но это не сработает, если количество элементов очень велико. Он переполнится. Были также предложения относительно использования XOR gate dup = dup ^ arr[i] ^ i, которые мне не понятны.

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

for i=0 to n-1
  begin :
    diff = A[i] - i;
    sum  = sum + diff;
  end

diff содержит дублирующий элемент, но с помощью этого метода я не могу найти индекс дублирующего элемента. Для этого мне нужно снова пройти массив, что нежелательно. Может ли кто-нибудь придумать лучшее решение, которое не связано с методом добавления, или метод XOR работает в O (n)?

Ответ 1

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

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

XOR ассоциативно, поэтому (x ^ y) ^ z = x ^ (y ^ z)
XOR коммутативна: x ^ y = y ^ x
XOR является его собственным обратным: x ^ y = 0, если x = y
XOR имеет нуль как тождество: x ^ 0 = x

Свойства (1) и (2) здесь означают, что при принятии XOR группы значений не имеет значения, какой порядок вы применяете XOR к элементам. Вы можете изменить порядок элементов или сгруппировать их по своему усмотрению. Свойство (3) означает, что если вы XOR одно и то же значение вместе несколько раз, вы получаете нулевое значение, а свойство (4) означает, что если вы XOR ничего с 0, вы получите свой исходный номер. Принимая все эти свойства вместе, вы получаете интересный результат: если вы принимаете XOR группы чисел, результатом является XOR всех чисел в группе, которые появляются нечетное число раз. Причиной этого является то, что когда вы XOR вместе цифры, которые появляются четное количество раз, вы можете разбить XOR этих чисел на набор пар. Каждая пара XOR равна 0 на (3), а затем комбинированный XOR всех этих нулей возвращает ноль по формуле (4). Следовательно, все числа четной кратности сокращаются.

Чтобы использовать это для решения исходной проблемы, выполните следующие действия. Во-первых, XOR объединяет все числа в списке. Это дает XOR всех чисел, которые появляются нечетным числом раз, что заканчивается тем, что все числа от 1 до (n-1), за исключением дубликата. Теперь, XOR это значение с XOR всех чисел от 1 до (n-1). Затем все числа в диапазоне от 1 до (n-1), которые ранее не были отменены, отменяются, оставляя только дублируемое значение. Более того, это выполняется в O (n) времени и использует только O (1) пространство, поскольку XOR всех значений вписывается в одно целое.

В исходном посте вы рассмотрели альтернативный подход, который работает, используя тот факт, что сумма целых чисел от 1 до n-1 равна n (n-1)/2. Однако вы были обеспокоены тем, что это приведет к переполнению целых чисел и вызовет проблему. На большинстве машин вы правы, что это вызовет переполнение, но (на большинстве машин) это не проблема, потому что арифметика выполняется с использованием целых чисел с фиксированной точностью, обычно 32-разрядных целых чисел. Когда происходит переполнение целых чисел, результирующее число не имеет смысла. Скорее, это просто значение, которое вы получили бы, если бы вы вычислили фактический результат, а затем сбросили все, кроме самых низких 32 бит. Математически это называется модульной арифметикой, а операции в компьютере выполняются по модулю 2 ³². В более общем смысле, пусть говорят, что целые числа хранятся по модулю k для некоторого фиксированного k.

К счастью, многие из арифметических законов, которые вы знаете и любите от обычной арифметики, все еще сохраняются в модульной арифметике. Нам просто нужно уточнить нашу терминологию. Мы говорим, что x конгруэнтно y по модулю k (обозначается x & equiv; _k y), если x и y оставляют один и тот же остаток при делении на k. Это важно при работе на физической машине, поскольку, когда на большинстве аппаратных средств происходит переполнение целочисленного числа, результирующее значение соответствует истинному значению по модулю k, где k зависит от размера слова. К счастью, в модульной арифметике справедливы следующие законы:

Например:

Если x & equiv; _k y и w & equiv; _k z, то x + w & equiv; _k y + z
Если x & equiv; _k y и w & equiv; _k z, то xw & equiv; _k yz.

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

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

Если вам не гарантировано, что ровно один элемент дублируется, и вы не можете изменить массив элементов, тогда проблема будет намного сложнее. Это классическая (и сложная!) Проблема интервью, которая, как сообщается, взяла Дон Кнут 24 часа, чтобы решить. Хитрость заключается в том, чтобы уменьшить проблему до экземпляра циклического поиска, рассматривая массив как функцию из чисел 1-n на 1- (n-1), а затем ищет два входа для этой функции. Однако полученный алгоритм, называемый алгоритм поиска циклов Floyd, чрезвычайно красив и прост. Интересно, что это тот же алгоритм, который вы использовали бы для обнаружения цикла в связанном списке в линейном времени и постоянном пространстве. Я бы рекомендовал посмотреть его, так как он периодически появляется в опросах по программному обеспечению.

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

Надеюсь, это поможет!

Ответ 2

Добавление элементов отлично, вам просто нужно взять mod (%) промежуточной совокупности при вычислении суммы элементов и ожидаемой суммы. Для операции mod вы можете использовать что-то вроде 2n. Вы также должны зафиксировать значение после вычитания.