好用的算法技巧6、找出两个没有重复的数

2019年6月10日10:23:13 发表评论 98 views

6、找出两个没有重复的数

对于第一题【找出没有重复的数】

给你一组整型数据,这些数据中,其中有一个数只出现了一次,其他的数都出现了两次,让你来找出一个数 。

有人问如果有2个数出现了一次,其他数都出现了一次,那还能用位运算来找出这两个数吗?

答是必须的,假如这两个出现一次的 数 分别为 A, B,则所有 数 异或后的结果为 A^B,这时我们遇到的问题是无法确定 A,B的值。

由于 A 和 B 是不一样的值,所以 A^B 的结果不为 0,也就是说,这个异或值的二进制中某一位为1。显然,A 和 B 中有且仅有一个数的相同位上也为 1

这个时候,我们可以把所有 数 分为两类,一类在这个位上为 1,另一类为 0,那么对于这两类,一类会含有 A,另一类会含有 B。于是,我们可以分别计算这两类 数 的异或值,即可得到 A 和 B 的值。

作者:帅地
来源:知乎

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: