※ 引述《RockLee (Now of all times)》之銘言： : 原始網址: : http://www.careercup.com/question?id=15381730 : 題目: : Given a document and a query of K words, : how do you 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). : Could someone propose an algorithm in O(n)? : 假設 occurrrences lists 是 sorted, 用 TreeMap 應可在 O(N*logK) 解決, : 一開始將每個 occurrrences list 最小的丟入 TreeMap 就可得到第一個 window, : (key = index in the document, value = the occurrrences list it belonged & its : index in that occurrrences list), : 之後將 TreeMap 最小的移除並加入同一個 occurrrences list 的下一個即可移動 : window, : 直到任一個 occurrrences list 耗完. : 但要在 O(N) 的時間內解決就想不出來了... : 不知道板上有沒有人有什麼 idea? Sorry, I can't understand your writing. Also, the link seems to be wrong... Can you describe it, step by step. For example, there are only 3 words, (a,b,c) how are you going to find the window, for the document [b b a c b b b b c b b a] ? --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 76.170.77.243