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

grf1973

比较一下。

1. Sub test()
   
2.     Dim A, B, i, x
   
3.     A = Array(1, 2, 3, 4, 5)
   
4.     B = Array(1, 5, 4, 3)    '自己改
   
5.     For i = 0 To UBound(B)
   
6.         x = x Xor B(i) Xor A(i)
   
7.     Next i
   
8.     MsgBox x Xor A(i)
   
9. End Sub

复制代码

上清宫主

10楼这代码好，思路决定出路

爱疯

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

群子老师！
t = m + 1 '此为范围内2个数的均值


我不明白，这句是想做啥{:041:}

香川群子

发现还可以更简单。
因为从1开始的每一组连续4个数的Xor都是可以抵消的。

1. Function f&(n1&, Optional n2& = 0) 'f=(m+1) Mod 4
   
2.     Dim i&, n&, x&
   
3.     If n2 = 0 Then
   
4.         f = (n1 + 1) Mod 4
   
5.     Else
   
6.         If n2 - n1 < 4 Then
   
7.             For i = n1 To n2
   
8.                 x = x Xor i
   
9.             Next
   
10.         Else
    
11.             For i = n1 To n1 + 3 - n1 Mod 4
    
12.                 x = x Xor i
    
13.             Next
    
14.             For i = n2 + 1 - (n2 - 3) Mod 4 To n2
    
15.                 x = x Xor i
    
16.             Next
    
17.         End If
    
18.         f = x
    
19.     End If
    
20. End Function

复制代码

望帝春心

没看答案，看了各位大神的回复，感觉我天真的可笑，我还以为是个娱乐题目呢

爱疯

如何理解「异或」的含义？ - 计算机 - 知乎
https://www.zhihu.com/question/31116687





异或的定义：不同为true，否则为false

1）A xor A = 0
因为两个数的每一个二进制位都相同，所以结果每一位也都是0。

2）A xor 0 = A
当其中一个参数是0时，其实每一位都是在做或运算。

3）A xor A xor B = B
因为规律1和规律2，所以规律3成立。

4）xor满足结合律、交换律

给定一个集合S上的二元运算·，如果对于S中的任意a,b,c。满足:
a·(b·c) = (a·b)·c
则称运算·满足结合律。

给定一个集合S上的二元运算，如果对S中的任意a,b满足:
a·b = b·a
则称·满足交换律。



觉得这个链接不错，只想到这几个了。。。{:021:}

today0427

看你们解释的都看不懂

songdg

异或这个解析亮了：男性和女性能生出孩子，否则就不行。

爱疯

无标题.rar (15.3 KB, 下载次数: 2)

2016-12-25 10:53 上传

点击文件名下载附件



不知道 eqv怎么表示{:041:}

香川群子

上清宫主 发表于 2016-12-23 13:53
群子啊，测试过吗？你这个代码只在偶数个数据下成立吧？奇数个数据呢？

这个简单吧，只要稍微修改一下：
假设有n1 To n2 的连续正整数区间，遗漏了1个数，需要遍历一次完成检查，那么：
如果一共是偶数个数，那么取平均值t=n1+n2，检查结果遗漏值s=t-s
如果一共是奇数个数，那么平均值仍然取t=n1+n2，
但检查结果有2种，如果s<t/2则遗漏值=t/2-s ,如果s>t/2则遗漏值=t+t/2-s

模拟代码：

1. Sub test1(n1&, n2&, r&)
   
2.     Dim i&, s&, t&
   
3.     t = n1 + n2
   
4.     For i = n1 To n2
   
5.         If i <> r Then s = s + i: s = s Mod t
   
6.     Next
   
7.     If t Mod 2 Then s = t - s Else s = t / 2 - s: If s < 0 Then s = t + s
   
8. '    Debug.Print r; s
   
9. End Sub

复制代码

简单测试：

1. Sub test_1()
   
2.     Dim a(), b(), i&, s&, t&
   
3.     a = Array(1, 2, 3, 4, 5, 6, 7)
   
4.     b = Array(3, 2, 7, 1, 6, 5)
   
5.    
   
6.     t = 1 + 7
   
7.     For i = 0 To 5
   
8.         s = s + b(i): s = s Mod t
   
9.     Next
   
10.     If t Mod 2 Then s = t - s Else s = t / 2 - s: If s < 0 Then s = t + s
    
11.     MsgBox s
    
12. End Sub

复制代码