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

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);

谢谢.

Answer 1

直观的猜测是,最佳序列的"中心"将是算术平均值,但事实并非如此.让我们用一些矢量数学找到正确的解决方案:

第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是你也没有说明是否应该区别对待负数.)

定理:连续数字必须位于最小和最大数字之间.[证据留给读者]

第2部分:现在回到我们的例子,假设我们采取了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,+ c也是产生差值1的算术序列的答案.为了尽量减少"步骤"的数量,我们必须选择一个合适的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轴之间的区域).这不是平均值(将最小化标准偏差或RMS误差,而不是绝对误差).为了找到最小化c,我们将其视为一个函数并考虑其导数.如果差异都远离x轴(我们试图制作101 112 103 114 105 116),那么只是不添加这些额外的东西是有意义的,所以我们将功能向下移向x轴.每当我们减少c时,我们将解决方案改进为6.现在假设其中一个*s通过x轴.每次我们减少c,我们将解决方案改进5-1 = 4(我们保存了5个工作步骤,但是必须*在x轴下面做一个额外的工作步骤).最终当HALF *超过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+86108步

*(我们通过使用我们的新目标重复步骤2,或者通过在先前差异的每个数字上加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步,与上述相同

如果您自己模拟这个,可以看到步数变为> 108,因为我们偏离范围[-5,-7].

伪代码:

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

蟒蛇:

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)

编辑:

事实证明,对于不同整数的数组,这相当于一个更简单的解决方案:选择一个(最多2个)中位数,假设它不移动,并相应地移动其他数字.如果您有任何重复项,这种更简单的方法通常会给出错误的答案,但是OP没有要求,所以这将是一个更简单,更优雅的解决方案.另外,我们可以使用我在此解决方案中给出的证据来证明"假设中位数不移动"解决方案如下:校正因子将始终位于数组的中心(即差异的中位数将是从数字的中位数).因此,任何可以保证这一点的限制都可以用于创建这种脑力激荡的变体.

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)))