一道coding面试题，大家有好的解法吗

数轴上有全是整数的n个点，这些点可以是重复的值，假如每移动一个点距离1需要的cost是1，问把所有点变成side-by-side(每两个点距离为1)需要的最小总cost。
例： [-4,1,4,4,6] 如果移动成  [1,2,3,4,5] 所需要的cost 是5+1+1+0+1=8 , 移动成 [2,3,4,5,6] 需要的cost是 6+2+0+1+0=9, 所以最小是8

有个leetcode hard题，是说把[n1, n2, n3, ..., nm]移动到某个值x，使得sum(abs(ni - x))最小，题号我忘了抱歉
其解法就是取中位数。最好理解的方法是数学归纳法：
不难证明数组是否有序不影响最终结果。假设[n1, n2, n3, ..., nm]已排序，其中位数为y，那么对于
1. 数组[n1, nm], 实际上n1~nm之间任何一点均可使得sum(abs(ni - x))最小，那么y也可以
2. 数组[n1, n2, n(m-1), nm]，那么n2~n(m-1)之间任何一点均可使得sum(abs(ni - x))最小，那么y也可以
3. 依此类推。若数组长度为奇数，中位数必然是其中点，那么[n1, ..., y, ..., nm] 取y必然可使得sum(abs(ni - x))最小

从这个题推广到你的问题，长度为m的数组A=[n1, n2, n3, ..., nm]，取合适的y值使得B=[y-m/2, ..., y-1, y, y+1, ..., y+m/2]的sum(abs(Ai-Bi))最小
那么它跟A=[n1+m/2, n2+m/2-1, ..., nm-m/2]，B=[y, y,..., y]的结果没有区别
那么它跟A=[n1-0, n2-1, ..., nm-m]，B=[y+m/2, y+m/2, ..., y+m/2]的结果没有区别
其结果就是ni-i的中位数

首先，这个题明显可以用答案集二分的方法解决
假设数组排序以后，最小的x，最大的y。。
并且最后得到的结果数组是[a, b]的闭区间

非常明显，当a==x 或者 b==y的时候，这个cost是最大的
所以，[x, y]这个区间里有最小值，直接在[x, y]里二分搜索左端点或者右端点就行
考虑排序，时间复杂度就是O(nlogn) + O(log(y-x)) -> O(nlogn)
=================================
其次，这个问题等价于

1. min (| x - x_1 | + | x+1 - x_2 | + .... + | x + (n-1) - x_n | )
   
2. w.r.t x

复制代码

同时，注意到 |a+b|<= |a| + |b|
上面的问题可以进一步转化为

1. min (| x - x_1 | + | x - x_2 | + .... + | x - x_n | )
   
2. w.r.t x

复制代码

这个优化问题可以直接通过gradient descent解决。。
这里abs value的梯度要用sub-gradient得到

1. d(|x|)/dx = sign(x)

复制代码

sign(x)有三种情况
1. x>0, sign(x) = 1
2. x=0, sign(x) = 0
3. x<0, sign(x) = -1

通过计算上面的梯度，就能得到最后的median是最优解

==========================
最后，值得记住的结论是
1. minimize sum of L1-distance (abs value)  ==> median
1. minimize sum of L2-distance (square value)  ==> mean

kevd 发表于 2023-12-20 13:15
我本来以为也是这样的，但是如果你看我题目给的那个例子 [-4,1,4,4,6], 如果取最中间的点不动（第一个4） ...

「一定有某个点不动」是正确的猜测，但是在这个例子里，真正保持不动的点是第二个4而不是最中间的（第一个4）。详情请参考我的回复。算法：

第一步：预处理，排序，然后各自减去下标（0到4），变成 [-4, 0, 2, 1, 2]，然后找到中位数1（在原始输入第2个4的位置），因此固定不动的数字是原始输入的第2个4。

最左边是ai-i的median，如果已经排序的话是线性复杂度

微信用户_k3yy2 发表于 2023-12-20 11:03
最左边是ai-i的median，如果已经排序的话是线性复杂度

请问ai-i 是什么原理呢

很显然一个点留在原地不动，左右两边的点都向它靠拢。那么只需要对每个点都算这个总距离就好。
便利每个点需要o(n) 对每个点求总距离如果优化是o(1) 具体优化方法是，对所有点排序，从左往右，一个点i 左面的总距离，是position(i) * 左面点的个数 - 左面所有点到分别到最左面的和。右边同样道理。

便利所有i个点，选择最小值就好。

补充内容 (2023-12-21 01:59 +08:00):
写错了 是(position(i) -最左面的点）

补充内容 (2023-12-21 02:02 +08:00):
思路没错，优化方法错了，早起昏头了 （不要看第二段，是错误的）

补充内容 (2023-12-21 02:02 +08:00):
但稍微改一下就好

如果点的顺序原本为 abcd...xyz，那么最优结果的顺序仍然是 abcd...xyz。不难用反证法证明。

我们要想办法移动最小距离，减少所有点之间的总距离（包括不相邻的点）。

所有的点应该朝着一个地方聚拢。这个地方显然不是右极也不是左极。这个地方实际上是最中间的点所在的位置。

nyufufu 发表于 2023-12-20 14:46
如果点的顺序原本为 abcd...xyz，那么最优结果的顺序仍然是 abcd...xyz。不难用反证法证明。

我们要想办法 ...

我本来以为也是这样的，但是如果你看我题目给的那个例子 [-4,1,4,4,6], 如果取最中间的点不动（第一个4）不动，其他点靠拢， 那么会得到[2 3 4 5 6], 但是这不是最优的。
答案就是一楼说的那样， 用所有的 ai-i 得到 [-4,0,2,1,2], 再求median=1， 再把这个数列与 median 做差 [5+1+1+0+1]. 但是我实在想不通为这么这么做

如果没有理解错题意的话，不太动脑筋的话，似乎可以用(答案)二分法？因为最终的递增数组的起始点的值应当介于原数组最小和最大值之间。

kevd 发表于 2023-12-20 13:15:21
我本来以为也是这样的，但是如果你看我题目给的那个例子 , 如果取最中间的点不动（第一个4）不动，其他点靠拢， 那么会得到, 但是这不是最优的。
答案就是一楼说

argmin_x(sum_i(abs((a_i-i)-(a_x-x)))) gives you median of a_i-i

kevd 发表于 2023-12-20 13:15:21
我本来以为也是这样的，但是如果你看我题目给的那个例子 , 如果取最中间的点不动（第一个4）不动，其他点靠拢， 那么会得到, 但是这不是最优的。
答案就是一楼说

中心点如果有重复确实会有不同，因为点需要往外挤而不是往内聚，所以需要预处理下，确实会比较麻烦。

我想了下，可以这么考虑这道题。
有一道 leetcode 经典题：9 个整数点 x，移动到相同位置的最小步数。
这题的思路是，假设终点为 a，那么结果是
｜x1-a｜+｜x2-a｜+...+｜x9-a｜的最小值
答案是中位数的点，证明过程略，谷歌一下即可。

本题的本质是 9 个整数点 x，移动到起点为 a，间隔为 1 的序列。
也就是求｜x1-a｜+｜x2-(a+1)｜+...+｜x9-(a+8)｜=求｜x1-a｜+｜(x2-1)-a)｜+...+｜(x9-8)-a｜的最小值

也就是说，本题可以转换为求整数点 x1，x2-1，x3-2，...，x9-8 这九个点
移动到相同位置的最小步数，结果是一样的。


补充内容 (2023-12-21 06:25 +08:00):
注意这里 x 是已知数，a 是未知数。

补充内容 (2023-12-21 06:38 +08:00):
fyi, leetcode 462 medium