如何找到一个重复的元素在一个洗牌连续整数数组？

我最近在什么地方碰到一个问题:

假设您有一个由1001个整数组成的数组。整数是随机排列的，但是您知道每个整数都介于1和1000之间(包括1和1000)。此外，每个数字在数组中只出现一次，除了一个出现两次的数字。假设只能访问数组中的每个元素一次。描述一种寻找重复数字的算法。如果在算法中使用辅助存储，是否可以找到不需要它的算法？

我感兴趣的是 第二部分，也就是 不需要使用辅助存储器。你有什么想法吗？

66171 次浏览
小开
最佳答案

只要把它们全部加起来，然后减去如果只使用1001个数字的话你所期望的总数。

例如:

Input: 1,2,3,2,4 => 12
Expected: 1,2,3,4 => 10


Input - Expected => 2
小开

把所有的数字加在一起。最后的和是1 + 2 + ... + 1000 + 重复的数字。

小开

把所有的数字加起来。整数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
for each element of the array:
sum += that element of the array
number_that_occurred_twice = sum - 500500
小开

没有额外的存储需求(除了循环变量)。

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

更新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
小开

引用弗朗西斯 · 潘诺夫的解决方案。

(通常)问题是: 给定一个任意长度的整数数组，其中只包含重复偶数次的元素，除了一个重复奇数次的值之外，找出这个值。

解决办法是:

acc = 0
for i in array: acc = acc ^ i

你现在的问题是适应。诀窍在于您要找到重复两次的元素，因此您需要调整解决方案来弥补这个缺陷。

acc = 0
for i in len(array): acc = acc ^ i ^ array[i]

这就是 Francis 的解决方案最终所做的，尽管它破坏了整个数组(顺便说一下，它只能破坏第一个或最后一个元素...)

但是，由于索引需要额外的存储空间，所以如果您还使用额外的整数，我认为是可以原谅的... ... 这种限制很可能是因为他们想阻止您使用数组。

如果它们需要 O(1)空间(1000可以看作 N，因为它在这里是任意的) ，那么它的措辞会更准确。

小开

弗朗西 · 佩诺夫的非破坏性解决方案。

这可以通过使用 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的解决方案 :)

这使用了一个额外的变量，因此不能完全满足问题中的要求。

小开

Python 中的一行解决方案

arr = [1,3,2,4,2]
print reduce(lambda acc, (i, x): acc ^ i ^ x, enumerate(arr), 0)
# -> 2

在 @ Matthieu M. 的回答中解释了它的工作原理。

小开

三角数 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
小开 
n = 1000
s = sum(GivenList)
r = str(n/2)
duplicate = int( r + r ) - s
小开

基于 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
小开

我支持添加所有元素，然后从中减去所有索引的总和，但是如果元素的数量非常大，这就不起作用了。也就是说。它会导致整数溢出！所以我设计了这个算法，它可以在很大程度上减少整数溢出的机会。

   for i=0 to n-1
begin:
diff = a[i]-i;
dup = dup + diff;
end
// where dup is the duplicate element..

但是通过这种方法，我将无法找到重复元素所在的索引！

为此，我需要遍历数组的另一个时间，这是不可取的。

小开 
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;
}
小开 
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);
}
小开

我对第二个问题的回答是:

求从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。

小开

在 aux 版本中，首先将所有值设置为 -1，并在迭代时检查是否已经将值插入 aux 数组。如果不是(值必须为 -1) ，则插入。如果你有一个副本，这里是你的解决方案！

在没有 aux 的列表中，从列表中检索一个元素，并检查列表的其余部分是否包含该值。如果里面有的话，你在这里找到了。

private static int findDuplicated(int[] array) {
if (array == null || array.length < 2) {
System.out.println("invalid");
return -1;
}
int[] checker = new int[array.length];
Arrays.fill(checker, -1);
for (int i = 0; i < array.length; i++) {
int value = array[i];
int checked = checker[value];
if (checked == -1) {
checker[value] = value;
} else {
return value;
}
}
return -1;
}


private static int findDuplicatedWithoutAux(int[] array) {
if (array == null || array.length < 2) {
System.out.println("invalid");
return -1;
}
for (int i = 0; i < array.length; i++) {
int value = array[i];
for (int j = i + 1; j < array.length; j++) {
int toCompare = array[j];
if (value == toCompare) {
return array[i];
}
}
}
return -1;
}

提交答案