电商网站的建设背景图片,如何做闲置物品交换的网站,免费crm手机版,上海传媒公司招聘艺人题目简介
一个数组中只有2个数字只有一个#xff0c;其他数字都有两个。找出这两个数字。a, b
用HashMap记录就不说了。
这里记录一下用异或的方式解决。
由于异或特性为自己异或自己为0。a^a 0;所以可以异或数组中的所有数字得出 a^b 的结果#xff0c;其他相同的都消掉…题目简介
一个数组中只有2个数字只有一个其他数字都有两个。找出这两个数字。a, b
用HashMap记录就不说了。
这里记录一下用异或的方式解决。
由于异或特性为自己异或自己为0。a^a 0;所以可以异或数组中的所有数字得出 a^b 的结果其他相同的都消掉了。又a ! b 因此a^b 的结果在二进制中肯定有一位是1。这个也好理解。下面就是我半天不能理解的点了。这里记录一下。
上面说a^b 肯定有一位是1。然后通过遍历数组的所有项以这一位是不是为1分成两组。
我就很纳闷理解了很久为什么以这个条件分成两组。
后来终于想到
因为a^b至少有一位是1的话那么在a 和b的二进制当中这一位一定是1个为0一个为1。
比如
a: xxx0xx, b: xxx1xx,
这样通过这一位去分组的话。就拿到两个数组分别存在a和b。这两个数组的其他项不用担心也一定是有重复可以异或成0的。
如
arr1: [a, 1, 1, 2, 2]; arr2: [b, 2, 2, 3, 3];
进一步理解既然a的这一位为0举例那么数组中其他这一位 为0的就不可能是b。
那我怎么知道其他这些数字能两两成对呢
因为这一位是0 的数字有一个满足的话那和他相同的那个数字也能满足。就一定是成对出现的。反证法了属于 这样通过遍历arr1 的所有项就能获取a的值了。
获取b的值也可以复用刚才a^b 的结果。使a^b^a b了 至于怎么获取这一位变成 0001000就看其他文章本文不做讨论。
代码就不放了。思路最重要。
