作者stimim (qqaa)
看板Prob_Solve
标题Re: [问题] Google Interview Question (4)
时间Thu Mar 7 09:19:08 2013
我也还没找到 O(n) 的作法，不过分享一下我到目前为止的想法。
首先假设这 K 个 occurrences list 各自是排序过的
lists = {list_1, list_2, ..., list_K}
where list_i = {p_i1, p_i2, ...}
不失一般性的假设 |list_1| (list_1 的元素个数) 是最小的
我们知道 the smallest window 一定会包含 p_11, p_12, ... 的其中一个
假设包含 p_1j
那对 list_i (i != 1) 来说，所要找的 window 一定会包含
a_i = max {p_ik | p_ik <= p_1j} 和
b_i = min {p_ik | p_ik >= p_1j} 的其中一个
於是，我们就可以得到一个小一点的问题，
lists = {list_1, list_2, ..., list_K}
where list_1 = {p_1j},
list_i = {a_i, b_i}
这个问题的大小是 O(K) ，如果可以在 O(K) 的时间得到答案的话，
我们就可以用 O(N) 的时间得到原问题的答案：
// all indices start from 1
Given lists
swap( lists[1], arg min { |lists[i]| } ) // O(N)
for i = 2, ..., K // This for loop can be done in O(N)
lists[i].push_back(INF) // 加入这两个边界可以让下面的程式简单
lists[i].push_front(-INF) // 一些
a = { 0, 0, ..., 0} // size = K
b = { 1, 1, ..., 1} // size = K
answer = INF
for i = 1, ..., |lists[1]|
for j = 2, ..., K
while lists[j][a[j] + 1] <= lists[1][i]
a[j] = a[j] + 1
while lists[j][b[j] + 1] >= lists[1][i]
b[j] = b[j] + 1
sub_lists[1] = { lists[1][i] }
for j = 2, ..., K
sub_lists[j] = { lists[j][a[j]], lists[j][b[j]] }
tmp = solve(sublists)
if (tmp < answer)
answer = tmp
return tmp
其中 a[j] = a[j] + 1 和 b[j] = b[j] + 1 的总运算量是 O(N)
所以，整个的运算量是
O(N) + O(N) + O(N) + O(|lists[1]| * O(solve(sublists))
如果 O(solve(sublists)) = O(K) 的话，因为 |lists[1]| <= N/K (因为他是最小的)
所以 O(|lists[1]| * O(solve(sublists)) = O(N)
整个的运算量就会是 O(N)
另外，因为 solve(sublists) 这个问题和原本的问题有很高的相似性，
如果原本的问题可以在 O(N) 的时间算完，
那 solve(sublists) 就可以在 O(K) 的时间算完。
反过来说，如果 solve(sublists)
不可能 在 O(K) 的时间算完
那原问题也
不可能 在 O(N) 的时间算完
(原命题为真，则逆否命题也为真)
很可惜的，解 sublists 我目前只想到 O(K logK) 的算法， O(K) 只能得到一些上界
补充1 ：
solve(sublists) 可以再换成另一个等价的问题：
给定 a = { a_1, ..., a_(K-1) }, b = { b_1, ..., b_(K-1) }
for all i, a_i, b_i >= 0,
a 和 b 并没有被排序过，且 a_i > 0 iff b_i > 0
目标：minimize A + B
subject to: for all i, either a_i <= A or b_i <= B
几个可以在 O(K) 算出来，可是不知道有没有用的东西：
max a_i (A <= max a_i)
max b_i (B <= max b_i)
max {min {a_i, b_i}}
a 的第 k 名
b 的第 k 名
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.4.176
1F：推 seanwu:不能sort or merge真的超烦orz 03/08 23:22
2F：→ seanwu:不过这篇这个结论挺强的说不定有机会XD 03/08 23:22
3F：→ seanwu:帮补个等价变形 {(ai,bi)} , ai<0, bi>0, i=1..K-1 03/08 23:23
4F：→ seanwu:求 min{ max{bj|(for all aj<ai)}-ai|(for all i)} 03/08 23:24