如何在混洗连续整数数组中find重复的元素？
我最近遇到了一个问题：
假设你有一个1001整数的数组。 整数是随机的，但是你知道每个整数在1到1000之间（包含）。 另外，每个数字在数组中只出现一次，除了一个数字出现两次。 假设你只能访问数组的每个元素一次。 描述一个algorithm来find重复的数字。 如果你在algorithm中使用了辅助存储，你能find一个不需要它的algorithm吗？
我感兴趣的是第二部分 ，即不使用辅助存储 。 你有什么主意吗？
只要把它们加起来，如果只用了1001个数字，就减去你所期望的总数。
例如：
Input: 1,2,3,2,4 => 12 Expected: 1,2,3,4 => 10 Input - Expected => 2 更新2：有些人认为使用异或来查找重复的数字是一个黑客或诡计。 我的官方回应是：“我不是在寻找一个重复的数字，我正在寻找一个重复模式的位数组，而且XOR确实比ADD更好地处理位集合”。 🙂
更新：只是为了好好睡觉之前，这里是“单线”替代解决scheme，需要零附加存储（甚至没有循环计数器），只接触一次数组元素，是非破坏性的，根本不能缩放： – ）
printf("Answer : %d\n", array[0] ^ array[1] ^ array[2] ^ // continue typing... array[999] ^ array[1000] ^ 1 ^ 2 ^ // continue typing... 999^ 1000 );
请注意，编译器将在编译时实际计算该expression式的后半部分，所以“algorithm”将在1002个操作中执行。
如果在编译时也知道数组元素的值，编译器会将整个语句优化为一个常量。 🙂
原始解决scheme：即使find正确答案，也不符合严格的问题要求。 它使用一个额外的整数来保持循环计数器，并且它访问每个数组元素三次 – 两次读取它并在当前迭代中写入，一次读取它以进行下一次迭代。
那么，你需要至less一个额外的variables（或一个CPU寄存器）来存储当前元素的索引，当你通过数组。
除此之外，这里是一个破坏性的algorithm，可以安全地扩展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
Franci Penov的非破坏性解决scheme。
这可以通过使用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.
该解决scheme的最大特点是不会遇到基于添加的解决scheme中出现的溢出问题。
由于这是一个面试问题，最好从基于添加的解决scheme开始，确定溢出限制，然后提供基于XOR的解决scheme:)
这使得使用一个额外的variables，因此完全不符合要求。
把所有的数字加起来。 最后的总和将是1 + 2 + … + 1000 +重复号码。
解释弗朗西斯·佩诺夫的解决scheme。
（通常）的问题是：给定一个任意长度的整数数组，只包含重复偶数次的元素，除了重复奇数次的一个值，找出这个值。
解决scheme是：
acc = 0 for i in array: acc = acc ^ i
你目前的问题是一个适应。 诀窍是你要find两次重复的元素，所以你需要适应解决scheme来弥补这个怪癖。
acc = 0 for i in len(array): acc = acc ^ i ^ array[i]
弗朗西斯的解决scheme到底是怎么做的，尽pipe它破坏了整个arrays（顺便说一句，它只能摧毁第一个或最后一个元素）
但是因为你需要索引额外的存储空间，所以如果你还使用了一个额外的整数，我想你会被原谅…这个限制很可能是因为他们想阻止你使用数组。
如果它们需要O(1)空间（1000可以被看作N，因为在这里是任意的），那么它就会被更精确地expression出来。
添加所有数字。 整数1..1000的总和是（1000 * 1001）/ 2。 与你得到的不同是你的号码。
如果你知道我们有1-1000的确切数字，你可以把结果加起来，并从sum(1, 1000)减去500500 （ sum(1, 1000) 500500 sum(1, 1000) ）。 这将给出重复的数字，因为sum(array) = sum(1, 1000) + repeated number 。
那么，有一个非常简单的方法来做到这一点… 1到1000之间的每一个数字只发生一次，除了重复的数字….因此，从1 … 1000的总和是500500。那么，algorithm是：
sum = 0
对于数组的每个元素：
sum + =数组的元素
number_that_occurred_twice =总和 - 500500
Python中的一行解决scheme
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; }
没有额外的存储要求（除了循环variables）。
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 ) );
参数和调用堆栈是否被视为辅助存储？
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); }
三angular形数T（n）是从1到n的n个自然数之和。 它可以表示为n（n + 1）/ 2。 因此，知道在给定的1001个自然数中，只有一个数是重复的，可以很容易地将所有给定的数相加并且减去T（1000）。 结果将包含这个重复。
对于一个三angular数T（n），如果n是10的任何幂，那么在基10的表示下find这个T（n）也是一个很好的方法：
n = 1000 s = sum(GivenList) r = str(n/2) duplicate = int( r + r ) - s
我支持添加所有的元素，然后从中减去所有的索引的总和，但是如果元素的数量非常大，这将不起作用。 也就是说会造成整数溢出！ 所以我devise了这个algorithm，可能会在很大程度上减less整数溢出的机会。
for i=0 to n-1 begin: diff = a[i]-i; dup = dup + diff; end // where dup is the duplicate element..
但通过这种方法，我将无法find重复元素存在的索引！
为此我需要遍历数组，这是不可取的。
基于XORing连续值的性质改进Fraci的答案：
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; }
或者在伪代码/mathlang 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
而在规范formsf（n）是：
f(0) = 0 f(n) = f(n-1) xor n
我对问题2的回答是：
find从1 – （到）N的数字的总和和乘积，说SUM ， PROD 。
find数字的总和和乘积1 – N- x – y，（假设x，y缺失），说mySum，myProd，
从而：
SUM = mySum + x + y; PROD = myProd* x*y;
从而：
x*y = PROD/myProd; x+y = SUM - mySum;
如果求解这个方程，我们可以findx，y。
