这是我一直在做的事情：
我有一个数字列表，例如 [1,2,3,4]
每一步我可以做 1 次操作：
我可以将列表中的数字减去 1
或者我可以将 1 添加到列表中的数字。
一个特殊情况是，如果元素变为0，那么你可以将其从列表中取出。在我的例子中，如果你从 1 减去 1，那么它就变成 0，列表就变成 [2,3,4]
目标是以尽可能少的步骤使列表同质化。
例如，对于 [1,2,3,4]，我们可以分 4 步到达 [2,2,2,2]，这是最快的。
我一直在尝试始终达到中位数，但它不起作用，例如有时删除列表中的一些数字比使其达到中位数更快，假设我们有 [1,4,4] 我们可以只需删除 1 即可得到 [4,4]。
我做的下一件事是测试每个元素 x 是否abs(x) 小于abs(median-x)。在这种情况下，我只需进行 x 操作以将其从列表中取出，否则我会将 abs(median-x) 计为该元素的最少操作数。
但它仍然不起作用，我可以得到一些关于如何做到这一点的见解吗？
首先，我们将证明具有最小步长的同质化列表应等于初始列表中的数字之一。
证明：
假设目标数
xa[i]sum(min(abs(x-a[i]), a[i]))s1然后我们考虑目标数字
x-1sum(min(abs(x-1-a[i]), a[i]))s2我们比较
s1s2s1 = s2s2 < s1s1s2 > s1x + 1x然后我们检查列表中的每个数字作为目标数字并计算所需的步骤，然后我们可以在
O(n^2)最佳解决方案并不总是中值。相反，我们需要尝试列表中最小和最大数字之间的每个可能的目标值。 对于每个潜在目标值，我们需要为每个数字考虑两个选项：
算法应该为每个数字选择更便宜的选项。 给定目标值的总成本是每个数字的最佳选择的总和。 然后我们选择总成本最小的目标值。
对于小整数列表，您可以在线性时间内解决此问题（使用计数排序），对于较大的值列表，可以在
O(n log(n))首先，让我们处理有符号值。数组的目标值可以为零、负数或正数。如果为零，则最小值只是数组值的总和。如果为正，则所有负值都接近于零，因此它们对总分的贡献将只是它们总分的绝对值。然后我们可以处理仅包含正值的子列表（对于负值情况反之亦然）。
要找到严格正列表的最小解，我们可以首先对列表进行排序，然后逐步从列表中删除最小值，将它们标记为归零，并将它们的数值添加到分数中。对于其余项目，我们仅计算中位数，并确定其余项目与中位数的总偏差。如果我们仔细地进行这个计算，我们可以用常数时间得到每个中值，在常数时间内计算剩余元素的子列表上与中值的组合（总和）偏差，并且可以在线性时间内整体计算出最小分数（不包括初始排序）。
在代码中，我们只需对列表进行排序，计算累积和，计算中位数，然后通过插入和修改数学迭代来计算每个分区的分数。这是执行此操作的 python 代码：
from itertools import accumulate
def solve_pos(nums):
if not nums:
return 0
nums = sorted(nums, reverse=True)
csums = list(accumulate(nums[::-1]))[::-1] + [0]
medians = [nums[i // 2] for i in range(len(csums))]
def score(size, median):
mid = size // 2
total = csums[0] - 2 * csums[mid] + 2 * csums[size]
total -= median * (2 * mid - size)
return total
return min(score(size, median)
for size, median in enumerate(medians))
def solve(nums):
neg = [x for x in nums if x < 0]
pos = [x for x in nums if x > 0]
return min(sum(map(abs, nums)),
-sum(neg) + solve_pos(pos),
sum(pos) + solve_pos([-x for x in neg]))
在Python中，由于排序函数的实现，这将是
O(n log n)O(n)