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

nyufufu 发表于 2023-12-20 16:18
中心点如果有重复确实会有不同，因为点需要往外挤而不是往内聚，所以需要预处理下，确实会比较麻烦。

我 ...

非常有道理

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

「保持顺序不变，原本的中位数还是新的中位数」不等于「保持最中间的点不动」！中间的点可以平移的，只需要仍然保持在中间即可

首先，最优解未必唯一，但一定是有限个。这个有限性接下来会用到。

其次，用反证法证明，最终的最优解的n个点之中，至少存在一个点的移动距离为0。证明：假设最优解A里面所有n个点都被移动了，那么不是向左就是向右，而且各个点移动的距离至少是1。记n个点之中有m个点向左移动、n-m个点向右移动。如果m大于等于n-m，那么构造一个新的解B，它相比A整体向右移动1格；如果m小于n-m，那么构造新的解B，它相比A整体向左移动1格。可以发现，B一定不比A差（这是因为，每个点的cost的改变量只能是-1或1，且个数分别是m和n-m）。所以，B也是最优解之一。现在，如果B里面有某个点的cost是0，那么我们就得到了一个「至少有一个点不被移动」的解；否则，把B作为A，重复上述步骤，直到得到一个「至少有一个点不被移动」的解（由于最优解只有有限个，这个算法一定能终止）。

这样，问题就转换成了，固定哪一个点，可以得到最优解呢？这样，已知至少有一个点是不动的，搜索空间大幅减小。即使最差的算法，也足够在O(N^2)的时间内找到最优解了。进一步的优化就交给楼下了。

补充内容 (2023-12-22 15:25 +08:00):
另外，楼上说了，最优解一定会保持原始输入的顺序（重复的点可以视为有一个内置的编号顺序）。证明也是调整法，对于现有的最优解A，假如里面原始输入a与b（a小于等于b）被移动到了位置x和x+1，那么cost是 abs(a-x) + abs(b-(x+1))，而构造新的解B，调换顺序，cost是 abs(a-(x+1)) + abs(b-x)，可以发现B一定不比A差。

如果结合这个性质，再结合我上面说的「一定有一个点没有移动」，那么很容易设计一个O(N^2)的算法：对每个数字，就假定它是固定的，然后利用保持顺序的性质，就能得到一个左右两侧数量与原始输入一致的解，计算这个解的cost，最后取最小的。如果要进一步优化，可以发现这里面重复计算很多，似乎可以用滑动窗口来做，只计算增量。这样就得到了O(N)复杂度的算法，即等价于：先把输入数组预处理，排个序，然后构造新数组 b[i] = a[i] - i。在b[i]数组上，问题就转化为了经典的求中位数。

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。

感觉是two pointer， o(n)复杂度吧，直接一个一个往后排就好了，因为你移动任何一个数字的cost都是相等的，所以不用考虑哪些点动哪些点不动

补充内容 (2023-12-23 03:04 +08:00):
哦，不对，开始数组不一定sort过，所以先sort再一个一个点往后排就好了，nlogn复杂度

首先，这个题明显可以用答案集二分的方法解决
假设数组排序以后，最小的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

这个先算加权平均值，然后围绕这个平均值分布两侧。

vincent_great 发表于 2023-12-23 02:10:54
首先，这个题明显可以用答案集二分的方法解决
假设数组排序以后，最小的x，最大的y。。
并且最后得到的结果数组是的闭区间

二分不是要求单调性吗 二分最短cost的和可以但你这个二分端点是不是没什么道理。。