※ 引述《stimim (qqaa)》之铭言： : 刚刚和 Leon 讨论了一下，发现我们对题目的了解有一点不同 : 原题目： : Given a document and a query of K words, how do u find the smallest window : that covers all the words at least once in that document? (given you know the : inverted lists of all K words, that is, for each word, you have a list of all : its occurrrences). This one is really hard. Could someone propose an : algorithm in O(n)? : 我们可以确定： : 1. document is given : 2. 知道我们关心的是哪 K 个字 : 3. 这 K 个字的 occurrence list 也是给定的 : 问题是，n 指的是什麽？ : 1. n = document size (in number of words) : 在这种情况下， O(n) 是可能的，方法基本上就是 Leon 提出来的。 恕删. 我觉得那个 N 的定义比较有可能是 document length.. 不过下面那个定义, 我想我的方法应该也可以啦. Here is the modification. : 2. n = 这 K 个字出现的总次数 : Ex: : K = 3, 要找出包含 {a, b, c} 的最小 window : occurrences: : a = { 1, 1000, 2500} : b = {400, 1001, 2000} : c = {500, 1002, 1500} : document size = 2500 甚至更高 (其他的位置是其他的字) : n = 3 + 3 + 3 = 9 而不是 2500 : 在这种情况下，已知可以做到 O(n logK) (RockLee 写的方法) : 不过，在这种状况下，给定原本的 document 似乎就没什麽用了 : 而且在读入 input 时， : 读入原本的 document 会花掉 O(document size) 的时间 : 所以在和 Leon 讨论时，他对这种解释方法有一点怀疑 So, when you build the occurance list from document, actually you will have scaned this array first.. {1, 400, 500, 1000, .... 2500} which represents {a, b, c, a..} We need to keep this too. Call it "Show_list" Then, use my algorithm, the left boundary are choosen sequentally from "Show_list". The first step will be, choosing [1] as left, and use max-min{b, c} as right. The second step is, drop [1] and use "Show_list(2)" as a new left boudary. Now, you drop at most one element in the window. The need O(1) to find the right boundary and get back this element. Hope it helps. --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 142.136.126.103