c*****g
发帖数: 33 | 1 网上看到一道题 求O(n)的解法. n是document中的word数
You have a dictionary, D, that stores the positions of words in a document
by mapping words (strings) to positions in the document (arrays of ints.)
You also have a list of words, L. Your job is to find the shortest sequence
of words in the document that contains all the words in L.
E.g., if the document is "a b a c d x b a", then
D["a"] = [0 2 7]
D["b"] = [1 6]
...
If we are given that L=["a", "c", "x"]
Then we should return the start and end point of the shortest sequence that
contains all words in L, which is (2, 5). The best solution is in O(n)
complexity. | r*****s
发帖数: 74 | | b******7
发帖数: 92 | 3 算法思想：可以使用|L|大小的最小堆，同时维护堆的最大值，则range为(heap.top(),
max{heap}),最多迭代n-|L|次，得出最优range。
时间复杂度O(|L|) + O(n*log|L|) 由于|L|最多为128，故为O(n）
此算法前提为：D(c)从小到大排序
code：
typedef pair::iterator,vector::iterator> Itemtype;
struct ItemCompare{
bool operator()(const Itemtype & left, const Itemtype & right)
{
return *(left.first) > * (right.first);
}
};
pair minrange(unordered_map > & D, vector &
L)
{
pair result = make_pair(-1,-1);
vector temp;
int maxpos = -1;
for(auto it = L.begin(); it != L.end(); ++it)
{
auto findit = D.find(*it);
if(findit == D.end() || findit->second.empty()) return result;
temp.push_back(make_pair(findit->second.begin(),findit->second.end()
));
maxpos = max(maxpos, findit->second[0]);
}
priority_queue, ItemCompare> minheap(temp.
begin(),temp.end());
int minpos = *(minheap.top().first);
result = make_pair(minpos,maxpos);
while(true)
{
Itemtype minelem = minheap.top();
minheap.pop();
minelem.first++;
if(minelem.first == minelem.second)
break;
minheap.push(minelem);
maxpos = max(maxpos,*(minelem.first));
minpos = *(minheap.top().first);
if(maxpos - minpos < result.second - result.first)
result = make_pair(minpos,maxpos);
}
return result;
}
类似的题：
http://www.careercup.com/question?id=16759664 | c*****g
发帖数: 33 | 4 Yes, I have found the similar problem on leetcode "Minimum Window Substring"
But there is a little bit different. Here they provide the dictionary D
which shows the indexes each character appears. I couldn't think a way to
utilize it in order to get O(n) solution.
【在 r*****s 的大作中提到】
: leetcode上面要不然有原题，要不然有近似的题
: http://leetcode.com/onlinejudge#question_30
|
|
