Haskell:频繁的价值观

Question

我正在尝试使用Segment Tree 来解决频繁的值

这篇博客文章使用了类似的方法

我想将列表分成以下间隔:

-1 -1 1 1 1 1 3 10 10 10 变 (0, 2) (2, 6) (6, 7), (7, 10)

我有一个代码:

g s = map (\x->(head x, length x)) . group . sort $ s

但它没有给出正确的输出.

是否可以使用频繁的值？

Answer 1

我会这样做的

f = neighbors . prefixSums . counts
  where
    counts = map length . group . sort
    prefixSums = scanl (+) 0
    neighbors xs = zip xs (tail xs)

这从计算counts元素开始,因此你的(任意排列)[-1, -1, 1, 1, 1, 1, 3, 10, 10, 10]变为[2, 4, 1, 3].

然后,prefixSums计算前缀的总和,因此我们得到[0, 2, 6, 7, 10]了我们的运行示例.

为了得到最终结果,我们只需连续输入neighbors此列表.