使整数数组连续所需的最小步骤

Question

给定一个排序的独特整数数组，使这些整数连续所需的最小步骤是什么？条件是：在一次步骤中，只能更改一个元素，并且可以通过增加或减少1来实现。例如，如果我们有2,4,5,6，那么可以将'2'变为'3'，从而使元素连续(3,4,5,6)。因此，这里的最小步骤是1。同样对于数组：2,4,5,8：

• 步骤1：'2' 可以变成 '3'
• 步骤2：'8' 可以变成 '7'
• 步骤3：'7' 可以变成 '6'

因此，序列现在是3,4,5,6，步骤数为3。

我尝试了以下代码，但不确定是否正确？

    //n is the number of elements in array a
    int count=a[n-1]-a[0]-1;
    for(i=1;i<=n-2;i++)
    {
        count--;
    }
    printf("%d\n",count);

感谢。

- pranay

---

由于您的解决方案没有查看a [1]..a [n-2]的值，因此它不可能是正确的。顺便说一下，您不应该在int中使用％lld。 - interjay

Answer 1

直觉上，最佳序列的“中心”将是算术平均值，但并非如此。让我们使用一些向量数学找到正确的解决方案：

第一部分：假设第一个数字不变（我们稍后再处理这个假设），计算差异，因此1 12 3 14 5 16-1 2 3 4 5 6将产生0 -10 0 -10 0 -10。

旁注：请注意，“连续”的数组根据您的“暗示”的定义将是具有差为1的递增算术序列。（请注意，对于您的问题，还有其他合理的解释：有些人可能认为5 4 3 2 1是连续的，或者5 3 1是连续的，或者1 2 3 2 3是连续的。 您也没有指定是否应特别处理负数。）

定理：连续数字必须位于最小和最大数字之间。[证明留给读者]

第二部分：回到我们的例子，假设我们采取了30步（sum(abs(0 -10 0 -10 0 -10))=30）来将1 12 3 14 5 16转换成1 2 3 4 5 6。这是一个正确的答案。但是0 -10 0 -10 0 -10+c也是一个答案，它产生了一个差为1的等差数列，其中常数项为c。为了最小化“步数”，我们必须选择一个适当的c。在这种情况下，每次增加或减少c，步数就会增加N=6（向量的长度）。例如，如果我们想将原始序列1 12 3 14 5 16转换为3 4 5 6 7 8（c=2），那么差值将会是2 -8 2 -8 2 -8，而sum(abs(2 -8 2 -8 2 -8))=30。

现在，如果你能将其形象化地描绘出来，那么这就非常清楚了，但在文字中难以表达。首先，我们取得了差向量。想象一下，你可以将它画成这样：

 4|
 3|     *
 2|  *  |
 1|  |  |  *
 0+--+--+--+--+--*
-1|           |
-2|           *

我们可以通过将所有元素加或减1来“移动”这个向量。这相当于找到c。我们希望找到使得您看到的 | 的数量最小的偏移量（即曲线与x轴之间的面积）。这不是平均数（那将是最小化标准差或均方根误差，而不是绝对误差）。为了找到最小的c，让我们将其视为一个函数，并考虑其导数。如果所有差异都远离x轴（我们正在尝试制作101 112 103 114 105 116），那么没有添加这些额外内容是有意义的，因此我们将函数向下移动到x轴。每次我们减少c，我们就可以提高6的解决方案。现在假设一个 * 超过了 x 轴。每次我们减少 c, 我们就可以通过4来提高解决方案(我们省去5个步骤的工作, 但必须为 * 在x轴下方做1个额外的步骤)。当一半的 * 超过了x轴时, 我们将无法进一步改善解决方案(导数: 3-3=0)。(事实上，很快我们开始使解决方案变得更糟，永远不能再改善它。我们不仅找到了这个函数的最小值，而且还可以看到它是全局最小值。)

因此解决方案如下: 假设第一个数字在其位置上。计算差值向量。通过找到差异的中位数并从差异中减去来最小化绝对值之和，以此来实现。得到一个改进后的差异向量。 "改进"向量的绝对值之和就是答案。这是O(N)。同样优秀的解决方案（如上所述）将始终是“相邻的”。只有在数字数量为奇数时才存在唯一解，否则如果数字数量为偶数，并且差异的中位数不是整数，则等效最优解将具有任何介于两个中位数之间的校正因子的差异向量。

所以我想最后给出一个例子。

1. 输入：2 3 4 10 14 14 15 100
2. 差分向量：2 3 4 5 6 7 8 9-2 3 4 10 14 14 15 100 = 0 0 0 -5 -8 -7 -7 -91
3. 注意到差分向量的中位数不再在中间，我们需要执行一个O(N)中位数查找算法来提取它们...
4. 差分向量的中位数是-5和-7
5. 让我们将-5作为我们的修正因子（任何介于中位数之间的数字，例如-6或-7，也是有效的选择）
6. 因此，我们的新目标是2 3 4 5 6 7 8 9+5=7 8 9 10 11 12 13 14，新的差分为5 5 5 0 -3 -2 -2 -86*
7. 这意味着我们需要做5+5+5+0+3+2+2+86=108步

我们可以通过重复第二步骤并使用新目标来获得这个结果，或者通过将前一个差值的每个数字加5来获得...但由于您只关心总和，所以我们只需将8*5（向量长度乘以正确因子）加到先前计算的总和中

或者，我们也可以将-6或-7作为我们的校正因子。假设我们取了-7...

• 那么新目标就是2 3 4 5 6 7 8 9+7=9 10 11 12 13 14 15 16，新差值将会是7 7 7 2 1 0 0 -84
• 这意味着我们需要进行7+7+7+2+1+0+0+84=108步，与上面相同

如果您自己模拟此过程，则可以看到步数随着偏移量远离范围[-5，-7]而变得大于108。

伪代码：

def minSteps(array A of size N):
    A' = [0,1,...,N-1]
    diffs = A'-A
    medianOfDiffs = leftMedian(diffs)
    return sum(abs(diffs-medianOfDiffs))

Python：

leftMedian = lambda x:sorted(x)[len(x)//2]
def minSteps(array):
    target = range(len(array))
    diffs = [t-a for t,a in zip(target,array)]
    medianOfDiffs = leftMedian(diffs)
    return sum(abs(d-medianOfDiffs) for d in diffs)

编辑：

事实证明，对于由不同的整数组成的数组，这等价于更简单的解决方案：选择一个（最多两个）中位数，假设它不动，然后移动其他数字。如果有任何重复项，则此简单方法通常会给出错误的答案，但问题并没有要求，因此这将是一种更简单、更优雅的解决方案。此外，我们可以使用我在此解决方案中给出的证明来证明“假设中位数不动”解决方案如下：校正因子将始终位于数组的中心（即差异的中位数将来自数字的中位数）。因此，任何保证这一点的限制都可以用来创建这个谜题的变化。

- ninjagecko

---

1. 请注意，问题已经说明输入是排序的。虽然这不会影响您的答案的正确性，但这意味着您的示例数据不符合要求。
2. 您能详细说明为什么算术平均数会使图形下面积最小化吗？这一点不太清楚。

- Weeble

@Weeble：我提供了一个输入已排序的示例。还有很好的发现！事实上，我的证明中存在错误，因此算术平均值并没有将图形下面的面积最小化；新答案证明了与“1,2,3,4，...”的差的中位数最小化了这个面积，并加以证明。你正好在我暂时删除答案来解决这个问题时插入了你的评论。=） - ninjagecko

看起来我们都在想同样的事情。我刚刚发布了一个答案，我认为它与您更正后的答案等效。 - Weeble

Answer 2

先找到所有数字的中位数。由于数字已经排序，这不应该是一个大问题。假设中位数不会移动。然后计算相应移动所有数字的总成本。这将给出答案。

社区编辑:

def minSteps(a):
    """INPUT: list of sorted unique integers"""

    oneMedian = a[floor(n/2)]

    aTarget = [oneMedian + (i-floor(n/2)) for i in range(len(a))]
      # aTargets looks roughly like [m-n/2?, ..., m-1, m, m+1, ..., m+n/2]

    return sum(abs(aTarget[i]-a[i]) for i in range(len(a)))

- Tejas Patil

---

完全正确。为了让答案更具体，这是算法：int median = a[n/2]; for( i=0; i < n; i++ ) { count += abs((median - n/2 + i) - a[i]); } - fishinear

@TejasP: 抱歉，我搞砸了我的示例。如果你考虑我在问题中使用的示例 [2, 3, 4, 10, 14, 14, 15, 100]，你的答案得到了124，但我认为答案应该是108？假设你实际上是指 @fishinear 所声称的 sum{i}(|median + (i-n/2) - a[i]|)，在我的情况下确实得到了相同的结果，但只有当你将两个中位数的平均值视为中位数时才有效（使用其中一个或另一个都会失败）。我相信它在 2 61 63 100 100 100 100 的情况下失败了，它声称需要171.5步（半步？），而我的方法声称需要165步。 - ninjagecko

@ninjagecko，你可能已经注意到了，OP提到了“排序的不同整数数组”。你的例子中没有显示出不同的整数。但我同意你的算法更加通用，因为它也考虑了重复的情况。顺便说一下，我展示的算法对于你最后一个例子需要174步。它永远不会产生半步，因为所有的东西都是整数。 - fishinear

@fishinear：啊，如果你说的是 x/y 意思是 floor(x/y)（或者在 Python 中是 x//y，不确定 C 中默认整数除法是否有效），那看起来确实可以正常工作！我已经模拟了所有长度为 6 和 10 的序列，其中数字唯一且排序在范围 [-6,6) 内。结果发现，你的答案和我的答案等价，因为数组是排序且唯一的，所以数字的中位数就是差值的中位数。我猜向上取整也可能有效。 - ninjagecko

我已经编辑了这个答案，使其更加清晰，并添加了Python的伪代码。 - ninjagecko

Answer 3

这可能不是最理想的解决方案，但这是一个初步的想法。

给定一个排序的序列 [x₁, x₂, …, x_n]:

• 编写一个函数，返回一个元素与前一个和后一个元素的差值，即(x_n – x_n–1, x_n+1 – x_n)。

• 如果与前一元素的差值 > 1，则必须将所有前面的元素增加x_n – x_n–1 – 1。也就是说，所需步骤的数量将增加以前元素数 × (x_n – x_n–1 – 1)。我们称此数字为a。

• 如果与后一个元素的差值 >1，则必须将所有后续元素减少x_n+1 – x_n – 1。也就是说，所需步骤的数量将增加以后元素数×(x_n+1 – x_n – 1)。我们称此数字为b。

• 如果a<b，则增加所有前面的元素，直到它们与当前元素相邻。如果a>b，则减少所有后续元素，直到它们与当前元素相邻。如果a=b，则无论选择这两个动作中的哪一个都没有关系。

• 将上一步骤中所采取的步骤总数相加（通过将必要步骤的总数增加a或b），并重复执行，直到所有元素都相邻。

- stakx - no longer contributing

Answer 4

首先，想象一下我们选择一个任意的连续递增值作为目标，然后计算修改数组以匹配该目标所需的成本（步骤数）。

Original:        3   5   7   8  10  16
Target:          4   5   6   7   8   9
Difference:     +1   0  -1  -1  -2  -7     -> Cost = 12
Sign:            +   0   -   -   -   -

因为输入的数组已经有序且不重复，所以它是严格递增的。因此，可以证明差值始终是非递增的。

如果我们将目标增加1，则成本会发生变化。当前差值为正数或零的每个位置都会增加1的成本。当前差值为负数的每个位置都会导致成本减少1：

Original:        3   5   7   8  10  16
New target:      5   6   7   8   9  10
New Difference: +2  +1   0   0  -1  -6     -> Cost = 10  (decrease by 2)

相反地，如果我们将目标减少1，那么每个当前差值为正数的位置都会导致成本降低1，而每个差值为零或负数的位置都会导致成本增加1：

Original:        3   5   7   8  10  16
New target:      3   4   5   6   7   8
New Difference:  0  -1  -2  -2  -3  -8     -> Cost = 16  (increase by 4)

为了找到目标数组的最优值，我们必须找到一个目标，使得任何变化（增加或减少）都不会降低成本。请注意，只有当负差异的位置多于零或正差异的位置时，目标的增量才能降低成本。只有当正差异的位置多于零或负差异的位置时，目标的减量才能降低成本。

以下是一些差异符号分布的示例。请记住，差异数组是非递增的，因此正数总是排在前面，负数排在后面：

        C   C
+   +   +   -   -   -       optimal
+   +   0   -   -   -       optimal
0   0   0   -   -   -       optimal
+   0   -   -   -   -       can increment (negatives exceed positives & zeroes)
+   +   +   0   0   0       optimal
+   +   +   +   -   -       can decrement (positives exceed negatives & zeroes)
+   +   0   0   -   -       optimal
+   0   0   0   0   0       optimal
        C   C

请注意，如果中央元素（标记为C）之一为零，则目标必须是最优的。在这种情况下，增加或减少任何值都不能改变成本，但可能会增加它。这个结果很重要，因为它给了我们一个简单的解决方案。我们选择一个目标，使得a[n/2]保持不变。可能有其他可能产生相同成本的目标，但肯定没有更好的目标。以下是修改后用于计算此成本的原始代码：

//n is the number of elements in array a
int targetValue;
int cost = 0;
int middle = n / 2;
int startValue = a[middle] - middle;
for (i = 0; i < n; i++)
{
    targetValue = startValue + i;
    cost += abs(targetValue - a[i]);
}
printf("%d\n",cost);

- Weeble

Answer 5

你不能仅通过一次迭代数组就做到这一点，这是肯定的。
首先需要检查每两个数之间的差异，例如：
2,7,8,9 可以是 2,3,4,5 用18步或者是 6,7,8,9 用4步。
创建一个新的数组来保存这些差值，例如对于 2,7,8,9 ，它应该是 4, 1, 1。现在你可以决定是否增加或减少第一个数字。

- Eran Egozi

Answer 6

假设连续数组看起来像这样 -

c c+1 c+2 c+3 ..等等

现在让我们举个例子 -

5 7 8 10

在这种情况下，连续的数组将是 -

c c+1 c+2 c+3

为了获得最小步骤，整数（之前和之后）与第i个索引的差的模的总和应该是最小的。在这种情况下，

(c-5)^2 + (c-6)^2 + (c-6)^2 + (c-7)^2 应该是最小的

让 f(c) = (c-5)^2 + (c-6)^2 + (c-6)^2 + (c-7)^2 = 4c^2 - 48c + 146

应用微积分以获得极小值，

f'(c) = 8c - 48 = 0 => c = 6

因此，我们的连续数组是6 7 8 9，这里的最小成本是2。

总之，只需生成f(c)，获取第一个微分并找出c即可。这将花费O(n)的时间。

- Suteerth

Answer 7

暴力枚举方法 O(N*M)

如果将数组a中的所有点都相互连线，则y0是每条线从索引0开始的值。答案是从a到每条以y0为起点的线所需步骤数的最小值，Python代码如下：

y0s = set((y - i) for i, y in enumerate(a))
nsteps = min(sum(abs(y-(y0+i)) for i, y in enumerate(a))
             for y0 in xrange(min(y0s), max(y0s)+1)))

输入

2,4,5,6
2,4,5,8

输出

1
3

- jfs