找到给定数组中的两个重复元素

Question

您将获得一个n + 2个元素的数组.数组的所有元素都在1到n的范围内.除了出现两次的两个数字外,所有元素都会出现一次.找到两个重复的数字.

例如,array = {4,2,4,5,2,3,1}和n = 5

伙计们我知道这个问题的4个可能的解决方案,但最近我遇到了一个我无法解释的解决方案.Below是解决方案的算法

traverse the list for i= 1st to n+2 elements
{
check for sign of A[abs(A[i])] ;
if positive then
   make it negative by   A[abs(A[i])]=-A[abs(A[i])];
else  // i.e., A[abs(A[i])] is negative
   this   element (ith element of list) is a repetition
}
Example: A[] = {1,1,2,3,2}
i=1 ; A[abs(A[1])] i.e,A[1] is positive ; so make it negative ;
so list now is {-1,1,2,3,2}

i=2 ; A[abs(A[2])] i.e., A[1] is negative ; so A[i] i.e., A[2] is repetition,
now list is {-1,1,2,3,2}

i=3 ; list now becomes {-1,-1,2,3,2} and A[3] is not repeated
now list becomes {-1,-1,-2,3,2}

i=4 ;
and A[4]=3 is not repeated

i=5 ; we find A[abs(A[i])] = A[2] is negative so A[i]= 2 is a repetition,

This method modifies the original array.

这个算法如何产生正确的结果,即它是如何工作的.人们不会把这作为一个家庭作业问题,因为这个问题最近在微软的采访中被问到过.

Answer 1

您将获得一个n + 2个元素的数组.数组的所有元素都在1到n的范围内.除了出现两次的两个数字外,所有元素都会出现一次

让我们稍微修改一下,然后单独使用n,而不是n+2问题语句的第一部分,它就变成了

您将获得一个包含n个元素的数组.数组的所有元素都在1到n的范围内

所以现在你知道你有一个数组,数组中的数字从1开始,并且对于数组中的每个项目都加一.因此,如果您有10个项目,则数组将包含数字1到10. 5个项目,您有1到5个项目,依此类推.

因此,存储在数组中的数字可用于索引数组.即你总能说出A[A[i]]我<= A的大小.例如A={5,3,4,1,2}; print A[A[2]]

现在,让我们添加一个重复的数字.该算法获取数组中每个数字的值,并访问该索引.我们知道如果我们两次访问相同的索引,我们知道我们发现了重复.
我们怎么知道我们是否两次访问同一个索引？
是的,我们改变了我们访问的每个索引中的数字符号,如果符号已经改变,我们知道我们已经在这里,因此,这个索引(不是索引中存储的值)是一个重复的数字.

您可以通过保留第二个布尔数组来实现相同的结果,初始化为false.那个algroithm变成了

A={123412}
B={false, false, false, false}

for(i = 1; i <= 4; i++)
{
    if(B[A[i]])
       // Duplicate
    else
       B[A[i]] = true;
}

但是在MS问题中,您正在更改A中元素的符号,而不是在B中设置布尔值.

希望这可以帮助,