支持二分查找求解LIS的最合适的数据结构是什么?
what is the most appropriate data structure supporting binary search to solve LIS?
我想用耐心排序算法解决 Haskell 中的 Longest increasing subsequence 问题。
我先是用列表做的,用了 O(n^2) 时间。
现在我想创建一个在 O(n log n) 时间内解决它的算法。为此,我需要在插入每个值 v
时获得“首次匹配”,换句话说,在 n log n[=27= 中找到最后一个元素大于 v 的第一堆] 时间。
data OrderedStruct = undefined -- ???
-- I need a method to remove elements in (n log n) time
popFirstBigger :: Ord a -> a -> OrderedStruct a -> (Maybe a, OrderedStruct a)
popFirstBigger a t = undefined
-- and one to insert them in (n log n) or faster
insert :: Ord a -> a -> OrderedStruct a -> OrderedStruct a
insert a t = undefined
我可以用平衡二叉搜索树来做,但我想知道它是否存在最短路线。
例如,我可以在二分搜索中使用的任何结构都足够了。
标准中是否存在这样的数据结构Haskell(例如Seq
?)
否则我可以使用哪种数据结构?
Data.Set
提供 insert
、delete
和 lookupGT
,全部在 O(log n) 时间内完成。
我想用耐心排序算法解决 Haskell 中的 Longest increasing subsequence 问题。
我先是用列表做的,用了 O(n^2) 时间。
现在我想创建一个在 O(n log n) 时间内解决它的算法。为此,我需要在插入每个值 v
时获得“首次匹配”,换句话说,在 n log n[=27= 中找到最后一个元素大于 v 的第一堆] 时间。
data OrderedStruct = undefined -- ???
-- I need a method to remove elements in (n log n) time
popFirstBigger :: Ord a -> a -> OrderedStruct a -> (Maybe a, OrderedStruct a)
popFirstBigger a t = undefined
-- and one to insert them in (n log n) or faster
insert :: Ord a -> a -> OrderedStruct a -> OrderedStruct a
insert a t = undefined
我可以用平衡二叉搜索树来做,但我想知道它是否存在最短路线。 例如,我可以在二分搜索中使用的任何结构都足够了。
标准中是否存在这样的数据结构Haskell(例如Seq
?)
否则我可以使用哪种数据结构?
Data.Set
提供 insert
、delete
和 lookupGT
,全部在 O(log n) 时间内完成。