×

Loading...

试试这个办法?

先排序,然后用二分法, 给每一个部分里面数列最长到最短的进行排序。
然后是merge, merge中把左子集和右子集已有的相差距离数列相加然后再统计一下从最多到最少就不用说了,必须做的,最关键的是要把大于子数列距离的数距离都要统计一边,当然这些新出现的距离是“最少的”因为才出现了1次么,但这个是这里的关键,否则会漏掉有可能会成为最长数列的距离,这一步有O(k^2)。

二分法是O(nlogn),但是merge用了O(k^2), 所以有可能会变成 O(n2) O(n^2logn) O(n^3),我没算啊,错了别骂我。
Report