这种方法不可取,因为它存在整数溢出问题。所以使用XOR
方法来查找这两个数字,它具有高性能。如果你感兴趣我可以解释一下。
根据下面来自@ordinary的请求,我将解释算法:
编辑
假设数组a[]
的最大元素是B
,即假设a[]={1,2,4}
,这里3
和5
不在a[]
中,因此最大元素是B=5
。
- 对数组
a
中的所有元素进行异或运算得到X
- 对从1到
B
的所有元素进行异或运算得到x
- 通过
x = x &(~(x-1));
找到x
的最左侧为1的位
- 如果
a[i] ^ x == x
,则将a[i]
与p
进行异或运算,否则与q
进行异或运算
- 现在对于从1到
B
的所有k
,如果k ^ x == x
,则将其与p
进行异或运算,否则与q
进行异或运算
- 现在打印出
p
和q
证明:
假设 a = {1,2,4}
且 B
是 5,即从 1 到 5 中缺失的数字为 3 和 5。
当我们对 a
中的元素和从 1 到 5 的数字进行 XOR
运算后,剩余的值为 3 和 5 的异或结果 x
。
现在,当我们找到 x
的最左边的位设置时,它实际上就是 3 和 5 中最左边不同的位。(3--> 011
,5 --> 101
,且 x = 010
其中 x = 3 ^ 5
)
接着,我们试图根据 x
的位设置将其分成两组,因此这两个组将是:
p = 2 , 2 , 3 (all has the 2nd last bit set)
q = 1, 1, 4, 4, 5 (all has the 2nd last bit unset)
如果我们对 p
的元素进行 XOR
操作,会得到 3
,同样地,如果我们对 q
的所有元素进行 XOR
操作,则会得到 5
。因此答案为:
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);
}
i
值,使得a[i+1]-a[i] != 1
。由于所示算法也必须遍历数组中的所有值,因此在数据有序时,二次方程式没有明显的优势。如果数据不能保证有序,则二次方程式的解需要线性时间(O(N)),而排序的解需要 O(N.log(N))的时间。 - Jonathan Leffler