使用XOR运算符的数组中找到重复的元素在许多情况下失败 [英] Using XOR operator for finding duplicate elements in a array fails in many cases

问题描述

我碰到一个帖子<少时href=\"http://stackoverflow.com/questions/2605766/how-to-find-a-duplicate-element-in-an-array-of-shuffled-consecutive-integers\">How找到洗牌连续整数数组重复的元素？但后来意识到，失败了很多投入。

I came across a post How to find a duplicate element in an array of shuffled consecutive integers? but later realized that this fails for many input.

有关前：结果
改编[] = {601,602,603​​,604,605​​,605,606,607}

#include <stdio.h>
int main()
{
int arr[] = {2,3,4,5,5,7};
int i, dupe = 0;
for (i = 0; i < 6; i++) {
    dupe = dupe ^ a[i] ^ i;
}
printf ("%d\n", dupe);
return 0;
}

我怎么能修改此code，这样重复的元素可以为所有的情况下发现了什么？

How can I modify this code so that the duplicate element can be found for all the cases ?

推荐答案

从原来的问题：

假设你有1001整数数组。该整数是按随机顺序，但你知道每个整数为1和1000（含）之间。此外，每个编号的数组中只出现一次，除了一个号码，发生两次。

Suppose you have an array of 1001 integers. The integers are in random order, but you know each of the integers is between 1 and 1000 (inclusive). In addition, each number appears only once in the array, except for one number, which occurs twice.

这基本上说，该算法只有当你有连续的整数，从1开始，用在某些N结束。

It basically says, that algorithm only works when you have consecutive integers, starting with 1, ending with some N.

如果你想修改它到更一般的情况下，你必须做以下的事情：

If you want to modify it to more general case, you have to do following things:

查找阵列最小值和最大值。然后计算期望的输出（XOR最小值和最大值之间的所有整数）。然后计算在阵列中的所有元素的异或运算。然后，异或这两样东西，你会得到一个输出。

Find minimum and maximum in array. Then calculate expected output (xor all integers between minimum and maximum). Then calculate xor of all elements in array. Then xor this two things and you get an output.

这篇关于使用XOR运算符的数组中找到重复的元素在许多情况下失败的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！