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
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.
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
a zero but if there’s an odd number of ones, we’ll wind up with a 1. So XORing all of those in
this case will give us a 1 here. Now what about this next bit here?
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 XOR with 1 is 0. And if we XOR all of these, again,
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.
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.