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

问题描述

我遇到了一个帖子 如何在洗牌的连续整数数组中找到重复元素?但后来意识到这对于许多输入都失败了.

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.

例如:
arr[] = {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
", dupe);
return 0;
}

如何修改此代码，以便在所有情况下都可以找到重复的元素?

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:

在数组中查找最小值和最大值.然后计算预期输出(异或最小值和最大值之间的所有整数).然后计算数组中所有元素的异或.然后对这两件事进行异或运算，你会得到一个输出.

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屋！