Written by 今天开始做题,第一个题目, Missing Number – New version .
发现我竟然在很短的时间内就想到了思路. 题目摘录如下:
An array A[1...n] contains all the integers from 0 to n except one. 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. Find the missing integer in O(n) time.
翻译成中文就是, 数组A[1..n] 包含 0-n 中的n-1个数, 只有一个不在里面. 数字以二进制存储,一次只能访问一位. (常数时间) . 现在要求在O(n)时间内找到不在其中的那个数.
下面是答案, 不想看答案的可以停止阅了.
————————————————
首先, 我们假设n =2k . (假设的合理性, 下面讨论) , 用k 位二进制数来表示一个数.
很显然所有数中i-th 位 会有n/2 个1 ,n/2 个 0.
init array T with 1..n
m = n-1
for i =1 to k
for j = 1 to m
B = []
C = []
if i-th-bit(A[j]) == 1
Add j to B
else
Add j to C
if size(B) < size(C)
T = B
else
T = C
m = floor(m/2)
Now T should only have one element k,
toogle last bit of A[k] is the missing number .
算法分析:
复杂度为 : n + n/2 + n/4 + n/8 + ……… + 2 + 1 < 2n = O(n)
不过使用了一些多余的存储空间.
另:n =2k假设的合理性.
if 2k-1 < n < 2k , 我们完全可以不管第一位, 因为它必定为1. (使用K位编码)
所以 T(n) = T(2k-1)
最近评论