程序员面试题100题(63)-数组中三个只出现一次的数字[算法].pdf，这是一份不错的文件
版权申诉
49 浏览量
2022-06-09
21:09:56
上传
评论
收藏 162KB PDF 举报
本文格式为 Word 版，下载可任意编辑
我们定义一个函数 f(n)，它的结果是保存数字 n 的二进制表示中
的最终一位 1，而把其他全部位都变成 0。比方十进制 6 表示成二进制
是 0110，因此 f(6)的结果为 2〔二进制为 0010〕。f(x^a)、f(x^b)、
f(x^c)的结果均不等于 0。
分析：我们商量了如何在一个数组中找出两个只出现一次的数字。
接着我们考虑 f(x^a)^f(x^b)^f(x^c)的结果。由于对于非 0 的 n，
在这道题中，假如我们能够找出一个只出现一次的数字，剩下两个只出
f(n)的结果的二进制表示中只有一个数位是 1，因此
现一次的数字就很简单找出来了。
f(x^a)^f(x^b)^f(x^c)的结果确定不为 0。这是因为对于任意三个非
假如我们把数组中全部数字都异或起来，那最终的结果〔记为 x〕
零的数 i、j、k，f(i)^f(j)的结果要么为 0，要么结果的二进制结果
就是 a、b、c 三个数字的异或结果〔x=a^b^c〕。其他出现了两次的数
中有两个 1。不管是那种状况，f(i)^f(j)都不行能等于 f(k)，因为
字在异或运算中互相抵消了。
f(k)不等于 0，并且结果的二进制中只有一位是 1。
我们可以证明异或的结果 x 不行能是 a、b、c 三个互不相同的数字
于是 f(x^a)^f(x^b)^f(x^c)的结果的二进制中至少有一位是 1。
中的任何一个。我们用反证法证明。假设 x 等于 a、b、c 中的某一个。
假设最终一位是 1 的位是第 m 位。那么 x^a、x^b、x^c 的结果中，有
比方 x 等于 a，也就是 a=a^b^c。因此 b^c 等于 0，即 b 等于 c。这与 a、
一个或者三个数字的第 m 位是 1。
b、c 是三个互不相同的三个数相矛盾。
接下来我们证明 x^a、x^b、x^c 的三个结果第 m 位不行能都是 1。
由于 x 与 a、b、c 都各不相同，因此 x^a、x^b、x^c 都不等于 0。
魏
第 1 页 共 3 页
程序员面试题 100 题(63)-数组中三个只出现一次的数
字[算法]
资源评论
sinat_40572875
- 粉丝: 52
- 资源: 7万+
下载权益
C知道特权
VIP文章
课程特权
VIP享7折，此内容立减5.97元 开通VIP
