一道面试题:有1-10亿数字的乱序数组，其中少一个数，怎么快速找到这个丢失的数

爱疯

这是在知乎上看到的，建议自己先想想，。。。。。。。。。。。。。最后 ，再看答案
反正我是没想到{:231:}




答案.rar (6.44 KB, 下载次数: 34)

2016-12-22 16:54 上传

点击文件名下载附件

望帝春心

1-10亿的和减去原所有数的和，差就是喽

香川群子

望帝春心 发表于 2016-12-22 17:03
1-10亿的和减去原所有数的和，差就是喽

把所有数加起来，也需要遍历所有数。但是不需要对检查结果进行再次遍历比较了。所以确实效率高一些。
考虑到1 - 10亿的和早已超过长整形数值范围，
所以模拟代码为：

    m = 10 ^ 9
    t = m + 1 '此为范围内2个数的均值
    For i = 1 To m
        s = s + a(i): If s > t Then s = s - t '如果累计和大于2数均值t则减去t、保证s不超过长整数范围
    Next
    MsgBox t - s '最后遗漏值=t-s

望帝春心

香川群子 发表于 2016-12-23 12:20
把所有数加起来，也需要遍历所有数。但是不需要对检查结果进行再次遍历比较了。所以确实效率高一些。
考 ...

收到，谢谢香川老师指点讲解

香川群子

看了答案，Xor 运算符好奇妙。

不过，想一想还是可以理解的。

C = A Xor B  比较运算得到的是A/B这2个二进制数之间不同的差异部分C，
因此 C Xor A = B 以及  C Xor B = A，也就是说可以随时还原另一个数。

而对于连续区间的数，当然可以各自抵消而把信息传承下去。

香川群子

1. Sub test()
   
2.     a = Int(Rnd * 10000)
   
3.     b = Int(Rnd * 10000)
   
4.     c = a Xor b   '计算a和b的Xor值c
   
5.     a1 = c Xor b '可通过c和b还原得到a
   
6.     b1 = c Xor a '可通过c和a还原得到b
   
7. End Sub

复制代码

上清宫主

香川群子 发表于 2016-12-23 12:20
把所有数加起来，也需要遍历所有数。但是不需要对检查结果进行再次遍历比较了。所以确实效率高一些。
考 ...

群子啊，测试过吗？你这个代码只在偶数个数据下成立吧？奇数个数据呢？

grf1973

我觉得跟连续区间无关，也不存在还原的问题
关键是xor和加减法一样有交换律的。
x XOR A(1)。。。。 XOR A(n) XOR B(1)  。。。 XOR B(n-1)  完全可以写成  
x XOR (A(i1) XOR B(i2))  XOR (A(m1) XOR B(m2)).......  XOR A(k)，
假设中间A(i1)=B(i2)。。。。。。，
那么 中间全部异或后，就剩下X=X xor A(K)了，结果就是A(K)
真的很妙。

香川群子

我研究了一下1-m的Xor运算的最后结果，具有规律性。

所以，可以简化计算，不必要循环1 - m

1. Function f&(m&)
   
2.     Dim i&, n&, x&
   
3.     n = m + 1
   
4.     While n > 3
   
5.         n = n - 2 ^ Int(Log(n) / Log(2))
   
6.     Wend
   
7.     For i = m - n + 1 To m
   
8.         x = x Xor i
   
9.     Next
   
10.     f = x
    
11. End Function

复制代码

原理：
在3个以上的连续整数中，每隔2^n个数的Xor值=0，
即0 - 2^n-1 的连续Xor值=0
则通过log计算求得最大2^n间隔以后，可以简化计算。

grf1973

原理和求和相减是一样的，只不过是在二进制下进行。

1. Sub test1()
   
2.     Dim A, B, i, s
   
3.     A = Array(1, 2, 3, 4, 9)
   
4.     B = Array(1, 9, 4, 3)    '自己改
   
5.    
   
6.     For i = 0 To UBound(B)
   
7.         s = s + A(i) - B(i)
   
8.     Next i
   
9.         
   
10.     MsgBox s + A(i)
    
11. End Sub
    

复制代码