ADM-201 dump PMP dumps pdf SSCP exam materials CBAP exam sample questions

算法:用位运算解决孤单整数的问题 – 译学馆
最新评论 (0)


Algorithms: Solve 'Lonley Integer' Using Bit Manipulation

嗨 我是《程序员面试金典》作者盖尔·拉克曼·麦克道尔
Hi, I’m Gayle Laakmann McDowell, author of Cracking the Coding Interview.
Today I’m going to cover the lonely integer problem.
一个整数数组 所有数都成双成对
So suppose we have an array of integers and all the numbers appear twice
except for one number that only appears once.
So how do we find that number, the lonely integer?
方法一是用哈希表 将所有元素储存在哈
Well one way is using a hashmap. So we can store all the
希表里 计算每个字符或整数的出现次数
elements in a hashmap and count how many times each character appears, or each
integer appears, and if something only appears once then that is of course the lonely
但该如何降低空间复杂度呢 由于必须
integer. But how can we reduce the space complexity even further? We can’t reduce
访问所有元素 我们无法降低时间复杂度
the time complexity because well we have to touch every element anyway. So how can
we reduce the space complexity?
Well let’s think about these numbers in binary.
The reason why binary is a good
bet here is that if we want to reduce the space complexity
we’re probably talking about constant space and
that means we can’t keep really any data
方法外 我们并无多少其它数据结构可用
structures we don’t have that much else to work with other than some sort of
考虑一下位元 对于最后一个位元
crazy bit issue. So let’s think about the bits here. Consider just that last bit
若每个整数都出现两次 那么末位上
there. If every number appeared twice, and literally every single number, then we’d
1的个数就为偶数 若1的个数不是偶数
see an even number of ones. If we don’t see an even number of ones then
that means that there’s a one in that bit for the lonely integer.
So we could go through and actually count the number of ones.
另外还可以将所有数相异或 若1的个数
Another thing we could do is just XOR everything, because if there’s an even
为偶数 结果为0 则孤单整数末位为0
number of ones, we’ll wind up with a zero, which means that the lonely integer has
但若1的个数为奇数 将所有数相异或
a zero but if there’s an odd number of ones, we’ll wind up with a 1. So XORing all of those in
结果就为1 那么下一位元呢?
this case will give us a 1 here. Now what about this next bit here?
再次进行考察所得结果为1 若将这些数
Well if we explore all of these again we’re going to get a 1
相异或 结果为0 因为1的个数是偶数
and if we XOR all of these here we’re going to get a 0 because have an even number of ones and
1异或1得0 接着再将这些数相异或
1 XOR with 1 is 0. And if we XOR all of these, again,
若1的个数是偶数 这里有2个1
if we have an even number of ones, we have two 1s,
so we’re going to get a 0 here.
实际上 与其一个个地遍历位元
So what we can do actually, rather than walking
不如遍历整个列表 将所有整数相异或
through this bit by bit by bit, we can walk through our whole list, XOR all the
有趣的是 最后的结果正好就是孤单整数
values and interestingly that resulting
value will be the lonely integer. So implementing this is now almost trivial. We
首先 result初始值为0 然后
just have some result which starts off at zero, walk through each value in my
遍历数组 与所有整数相异或
array, and XOR everything together.
最后 返回result的值
And then just return my result. So bit
manipulation problems are often, are one of those problems that do kind of
题之一 一个建议是 如果你既要保持很
involve aha moments sometimes, so one tip off is if you’re asked to keep the
低的时间复杂度 又要降低空间复杂度
time complexity really really fast but still reduce the space complexity even
特别是常数时间的 有时你就需要用到
more, especially like for constant time, that sometimes where you’re going to want
位运算 另一个建议是 处理位运算题时
some bit manipulation approach. The other tip is when you are tackling a
与其一次考虑所有整数 不如一个位元一
bit manipulation problem, try looking at it bit by bit rather than with all
个位元的考虑 并考察不同操作带来的
the integers at once, and explore what the result of different operations like
结果 比如 与 异或 移位 记住这些
anding and XORing and shifting would give you. So keep those things in mind
并练习位运算题 一旦你克服畏难情绪
and you know, practice bit manipulation problems. They aren’t necessarily that hard once
并掌握窍门 它们就不再是那么难了
you get a hang of them, once you get over the like intimidation factor.
Good luck.