b******7
发帖数: 92 | 1 算法思想：可以使用|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);
v... 阅读全帖 |
|
