t*****a
发帖数: 106 | 1 编程菜鸟，面了一下CISCO.一道很简单的题。一个Sorted array A,元素是数字1~N，一
个数字丢失，如何最快的找到丢失的数字。我的算法是binary search，先比较A[(n-1)
/2]==1+(n-1)/2， 相等，丢失数字在右侧，否则在左侧，递归可得O(log(N))的算法。
但interviewer说我的算法不够快，应该数0,1个数，做bit manipulation。但bit
manipulation也是O(N)的复杂度啊。哪位大侠能解释一下如何用bit manipulation达到
比O(log(N))更优的时间复杂度啊。 |
e*****i
发帖数: 182 | 2 简单来说，你的算法是错的，怎么lgn法啊，看一半如何知道哪一半丢了啊？ |
e*****i
发帖数: 182 | 3 没看到sorted不好意思！
不过觉得题目不可能是sorted！ |
w*********0
发帖数: 147 | 4 是不是bit manipulate位运算更tricky一些，其次更简单。 |
t*****a
发帖数: 106 | 5 确实是sorted，如果不是sorted那就是直接XOR了，我double check了，开始我说可以
XOR,他说对这个specific question, sorted的array,该如何做。这个肯定没有听错。
【在 e*****i 的大作中提到】
: 没看到sorted不好意思！
: 不过觉得题目不可能是sorted！
|
t*****a
发帖数: 106 | 6 我理解他的bit manipulation就是CC 150上的5.7题。
CC150上的题是这样的
"An array A[1…n] contains all the integers from 0 to n except for one
number which is missing. In this problem, we cannot access an entire integer
in A with a single operation. The elements of A are represented in binary,
and the only operation we can use to access them is “fetch the jth bit of A
[i]”, which takes constant time. Write code to find the missing integer.
Can you do it in O(n) time?"
但interviewer没说一次只能fetch 一位bit.实在想不出来有什么比O(log(N))更快的算
法了。
【在 w*********0 的大作中提到】
: 是不是bit manipulate位运算更tricky一些，其次更简单。
|
w*********0
发帖数: 147 | 7 不，我的想法bit manipulation是遍历数组的每个数的最后一位，即与1'b1做与。如果
是连续的应该就会得到0，1，0，1，0，1。。。。循环，但是漏一个数字就会出现0，0
.或者是1，1.再看该数字即可，这样是不是位运算更多一些，于是就简单点？菜鸟的一
点小想法。
1)
【在 t*****a 的大作中提到】
: 编程菜鸟，面了一下CISCO.一道很简单的题。一个Sorted array A,元素是数字1~N，一
: 个数字丢失，如何最快的找到丢失的数字。我的算法是binary search，先比较A[(n-1)
: /2]==1+(n-1)/2， 相等，丢失数字在右侧，否则在左侧，递归可得O(log(N))的算法。
: 但interviewer说我的算法不够快，应该数0,1个数，做bit manipulation。但bit
: manipulation也是O(N)的复杂度啊。哪位大侠能解释一下如何用bit manipulation达到
: 比O(log(N))更优的时间复杂度啊。
|
t*****a
发帖数: 106 | 8
，0
这种算法的本质是检测是否连续出现两个奇数，或者两个偶数，但算法复杂度还是O(N)
啊，不会比O(log(N))快。感觉那个interviewer自己没想明白，一般面试题O(log(N))
基本上就是能到达的最优了。
【在 w*********0 的大作中提到】
: 不，我的想法bit manipulation是遍历数组的每个数的最后一位，即与1'b1做与。如果
: 是连续的应该就会得到0，1，0，1，0，1。。。。循环，但是漏一个数字就会出现0，0
: .或者是1，1.再看该数字即可，这样是不是位运算更多一些，于是就简单点？菜鸟的一
: 点小想法。
:
: 1)
|
