问题描述
你是怎么做到这一点?该值是无序,但 [1..1]
例阵列 [3,1,2,5,7,8] $的C $ C>。答:
4,6
How do you do this? The values are unsorted but are of [1..n]
Example array [3,1,2,5,7,8]
. Answer: 4, 6
我看到这个解决方案的另一个类似帖子,但我不明白的最后一步
I saw this solution in another similar post, but I do not understand the last step
Find the sum of the numbers S=a1+...+an.
Also find the sum of squares T=a1*a1+...+an*an.
You know that the sum should be S'=1+...+n=n(n+1)/2
You know that the sum of squares should be T'=1^2+...+n^2=n(n+1)(2n+1)/6.
Now set up the following system of equations x+y=S'-S, x^2+y^2=T'-T.
Solve by writing x^2+y^2=(x+y)^2-2xy => xy=((S'-S)^2-(T'-T))/2.
And now the numbers are merely the roots of the quadratic in z: z^2-(S'-S)z+((S'-S)^2-(T'-T))/2=0.
什么是设置的解释在以Z为未知的最后一步二次方程?那是什么是解决这个问题呢?
What is the explanation for setting up that quadratic equation in the final step with z as the unknown? What's the intuition behind that being the solution to this problem?
推荐答案
这个方法是不可取的,因为它从整数
溢出问题受到影响。所以,使用 XOR
方法查找两个数字,这是非常高性能的。如果你有兴趣,我可以解释的。
This method is not advisable as it suffers from integer
overflow problems. So use XOR
method to find the two numbers, which is highly performant. If you are interested i can explain.
根据从@ordinary下面,我解释算法:
As per the request from @ordinary below, i am explaining the algorithm:
修改
假设数组的最大元素 A []
是 B
即假设 A [] = {1,2,4}
这里 3
和 5
不present在[]所以最大元素是 B = 5
。
Suppose the maximum element of the array a[]
is B
i.e. suppose a[]={1,2,4}
and here 3
and 5
are not present in a[] so max element is B=5
.
-
XOR
阵列中的所有元素A
到X
-
XOR
1的所有元素B
到X
- 找到最左边位组
X
按X = X及(〜(X-1));
- 现在,如果
A [1] ^ X = = X
比XOR
A [我]
到P
其他XOR
与①
- 现在,所有
K
1至B
如果K ^ x的== x
比XOR
与P
其他XOR
与①
- 现在,打印
P
和①
xor
all the elements of the arraya
toX
xor
all the elements from 1 toB
tox
- find the left most bit set of
x
byx = x &(~(x-1));
- Now if
a[i] ^ x == x
thanxor
a[i]
top
elsexor
withq
- Now for all
k
from 1 toB
ifk ^ x == x
thanxor
withp
elsexor
withq
- Now print
p
andq
证明:
让 A = {1,2,4}
和 B
5,即从1到5的缺失号是3和5
Let a = {1,2,4}
and B
is 5 i.e. from 1 to 5 the missing numbers are 3 and 5
在我们 XOR
的元素 A
我们留下的数字从1到5 XOR
3个和5个,即 X
。
Once we XOR
elements of a
and the numbers from 1 to 5 we left with XOR
of 3 and 5 i.e. x
.
现在,当我们找到了最左边位组 X
这只不过是最左边的不同位之间3和5(3-- <$ C C $> &GT; 011 , 5 - &GT; 101
和 X = 010
,其中 X = 3 ^ 5
)
Now when we find the leftmost bit set of x
it is nothing but the left most different bit among 3 and 5. (3--> 011
, 5 --> 101
and x = 010
where x = 3 ^ 5
)
在此我们试图根据位组 X
使两大集团将分为两组:
After this we are trying to divide into two groups according to the bit set of x
so the two groups will be:
p = 2 , 2 , 3 (all has the 2nd last bit set)
q = 1, 1, 4, 4, 5 (all has the 2nd last bit unset)
如果我们 XOR
的 P
它们之间的元素,我们会发现 3
,同样,如果我们 XOR
的①
所有彼此之间的内容比我们会得到5。因此,问题的答案。
if we XOR
the elements of p
among themselves we will find 3
and similarly if we xor
all the elements of q
among themselves than we will get 5.Hence the answer.
code在Java
public void findNumbers(int[] a, int B){
int x=0;
for(int i=0; i<a.length;i++){
x=x^a[i];
}
for(int i=1;i<=B;i++){
x=x^i;
}
x = x &(~(x-1));
int p=0, q=0;
for(int i=0;i<a.length;i++){
if((a[i] & x) == x){
p=p^a[i];
}
else{
q=q^a[i];
}
}
for(int i=1;i<=B;i++){
if((i & x) == x){
p=p^i;
}
else{
q=q^i;
}
}
System.out.println("p: "+p+" : "+q);
}
这篇关于找到2名失踪人数在整数数组有两个缺失值的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!