×

Loading...

试试这个办法?

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

二分法是O(nlogn),但是merge用了O(k^2), 所以有可能会变成 O(n2) O(n^2logn) O(n^3),我没算啊,错了别骂我。
(#10017807@0)
2016-3-29 -05:00
Reply
Page address has been copied.
To share, click to copy page address.
Share Online by QR Code

Back To Topic: 一道面试题,大家给出出主意哈,我一点头绪都没有

Back To Forum: HOME枫下论坛枫下论坛主坛工作学习学科技术