PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] Google Interview Question (4)

看板Prob_Solve (計算數學 Problem Solving)作者stimim (qqaa)時間11年前 (2013/03/07 09:19)推噓1(1推 0噓 3→)

留言4則, 1人參與討論串5/13 (看更多)

我也還沒找到 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