基于中位数的解法

shencode 2022-04-07 14:47:49 2022-04-07 14:49:29 14 返回题目

  • 由题意知要使原整数序列 变为连续序列的最小修改量,即求:的最小值

  • 稍作变换:,将更新为,则转化为求:的最小值。

  • 实际上,可将其视为在一条数轴上(对升序排序),找一个整数点使得到其距离和最小,该点可用的中位数即可。

时间复杂度为O(nlgn)。

{{ vote && vote.total.up }}