这一趣题和《算法新解》前言中的“最小可用Id”问题具有很多类似的地方。

有个从1到n的数字列表,经过某些处理后,发生了两点变化。1)序列的顺序被打乱了;2)其中一个数字x被篡改成了数字y,其中x和y都在1到n之间。能否找到一个线性时间,常数空间的方法,找出丢失的x和重复的y呢?

例如

[3, 1, 3, 5, 4] ==> x = 2, y = 3

分而治之

我们可以用中数m = floor((1 + n) / 2)将序列一分为二。将所有小于等于m的数字移动到左侧;将剩余的数字移动到右侧。

如果左侧的长度小于m,我们立刻得知丢失的数字在左侧,记s = 1 + 2 + ... + m = m(m + 1)/2,则x = s - sum(left)。同时,我们可以计算出重复的数字在右侧,记s' = (m + 1) + (m + 2) + ... + n = (n + m + 1)(n - m)/2,则y = sum(right) - s';

若左侧的长度大于m,我们立即得知重复的数字在左侧。使用同样的方法,可以算出丢失的数字x = s' - sum(right),重复的数字y = sum(left) - s;

否则,如果左侧的长度等于m,说明有m个不大于m的数字,但是我们不知道它们是否是1, 2, ..., m的某个排列。为此,我们可以计算并比较sum(left)和s。如果它们相等,说明左侧没有问题,我们可以丢弃左侧的所有数字,然后递归地在右侧寻找x和y;否则,我们丢弃右侧,在左侧递归寻找答案。

在递归查找时,我们需要用序列的下限替换上述步骤中的1。由于每次我们都去掉一半的列表,因此根据主定理,总时间复杂度为O(n)。同样,我们可以这样推导需要的时间:O(n + n/2 + n/4 + ...) = O(2n) = O(n)。

下面是对应的Haskell和Python的例子程序

Haskell的分而治之解法例子程序:

missDup xs = solve xs 1 (toInteger $ length xs) where
  solve xs@(_:_:_) l u | k < m - l + 1 = (sl - sl', sr' - sr)
                       | k > m - l + 1 = (sr - sr', sl' - sl)
                       | sl == sl' = solve bs (m + 1) u
                       | otherwise = solve as l m
      where
          m = (l + u) `div` 2
          (as, bs) = partition (<=m) xs
          k = toInteger $ length as
          sl = (l + m) * (m - l + 1) `div` 2
          sr = (m + 1 + u) * (u - m) `div` 2
          (sl', sr') = (sum as, sum bs)

使用Python,如果不希望每次递归时构造新的列表,我们可以使用就地(in-place)分割方法。这和快速排序中的N. Lomuto方法类似:

def partition(xs, l, u, x):
    left = l
    for right in range(l, u):
        if xs[right] < x:
            (xs[left], xs[right]) = (xs[right], xs[left])
            left = left + 1
    return left

def solve_inplace(xs):
    (l, u) = (0, len(xs))
    while l<u:
        m = (l+u)/2
        m1 = partition(xs, l, u, m)
        (nl, nr) = (m1 - l, u - m1);
        (sl, sr) = (sum(xs[l:m1]), sum(xs[m1:u]))
        sl1 = (l + m - 1)*(m - l)/2
        sr1 = (m + u - 1)*(u - m)/2
        if m1 < m:
            return (sl1 - sl, sr - sr1)
        elif m1 > m:
            return (sr1 - sr, sl - sl1)
        else:
            if sl == sl1:
                l = m1
            else:
                u = m1

这里还可以参考Scala的例子代码:https://github.com/liuxinyu95/AlgoXY/blob/algoxy/others/problems/miss-dup/MissDup.scala

鸽笼排序

由于所有的数字都在1到n之间,我们可以使用鸽笼排序来重新排列数字。我们自左向右扫描,对于每个位置i上的数字x,如果x不等于i,我们就将它和位置x上的数字y交换。如果x等于y,我们就找到了重复的数字,同时,我们得知丢失的数字就是i,我们重复这一交换过程,直到x等于i或者找到重复的数字。由于每个数字仅被交换一次以到达正确的位置,因此总时间复杂度为O(n)。

下面是相应的Python例子程序:

def solve3(xs):
    (miss, dup) = (-1, -1)
    for i in range(len(xs)):
        while xs[i] != i:
            j = xs[i]
            if xs[j] == xs[i]:
                dup = xs[j]
                miss = i
                break
            else:
                j = xs[i]
                (xs[i], xs[j]) = (xs[j], xs[i])
    return (miss, dup)

符号编码

假设存在一个长度为n的标记数组,对于序列中的每个数字x,我们都将标记数组中的第x个位置做上标记。当我们遇到重复元素时,我们会发现这个位置上的标记已经做过了。记重复的数字为d,我们知道s = 1 + 2 + ... + n = n * (n + 1) / 2,以及序列中所有的数字和s'。我们可以计算出丢失的数字m = d + s - s'。 但是这一方法需要额外长度为n的空间用作标记数组。由于数字的存在与否是一种二值化的信息(有、或没有),我们可以将其编码为数字的正负号,从而复用待查找的数字序列。对于序列中的每个数字x,我们将序列中第|x|位置上的元素标记为负数,其中|x|表示x的绝对值。如果发现某一位置已经为负了,我们就找到了重复的元素,接下来我们就可以计算出丢失的数字。

下面是根据这一思路给出的Python例子程序:

def solve4(xs):
    miss, dup = -1, -1
    n = len(xs)
    s = sum(xs)
    for i in range(n):
        j = abs(xs[i]) - 1
        if xs[j] < 0:
            dup = j
            miss = dup + n * (n + 1) / 2 - s
            break
        xs[j] = - abs(xs[j])
    return (miss, dup)

解方程

考虑一个简化的问题:给定一个从1到n的列表,去掉一个元素,然后打乱序列的顺序,怎样能够快速找出去掉的元素呢?我们可以将列表中所有的元素相加,然后从n * (n + 1) / 2减去这一结果就得出了答案。这一思路可以表示为如下方程:

m = s - s'

其中m表示丢失的数字,s是从1到n的累加和,s'是列表中所有元素的和。 但是,对于我们这里的问题,同时存在一个丢失的元素和一个重复的元素,我们无法仅用一个方程求出两个未知数。

sum(x[i] - i) = d - m ----(1)

其中右侧是列表中第i个元素减去i后的累加和。我们能否找出第二个独立的方程呢?思路是使用平方。如果我们将第i个元素的平方减去i的平方,然后将结果累加起来。就可以得到下面的结果:

sum(x[i]^2 - i^2) = d^2 - m^2 = (d + m) * (d - m) ----(2)

由于d - m不等于0,我们可以用式(2)除以式(1)两侧,得到另一个方程:

sum(x[i]^2 - i^2) / sum(x[i] - i) = d + m ----(3)

比较方程(1)和方程(3),我们有两个方程,两个未知数,这样就可以得到结果:

m = (sum(x[i]^2 - i^2) / sum(x[i] - i) - sum(x[i] - i)) / 2

d = (sum(x[i]^2 - i^2) / sum(x[i] - i) + sum(x[i] - i)) / 2

下面是基于这一思路的Python和Haskell例子程序

Python:

def solve2(xs):
    ys = zip(xs, range(len(xs)))
    a = sum(map(lambda (a, b): a-b, ys))
    b = sum(map(lambda (a, b): a*a - b*b, ys))
    return ((b/a - a)/2, (a + b/a)/2)

Haskell:

missDup' xs = ((b `div` a - a) `div` 2, (b `div` a + a) `div` 2) where
  ys = zip xs [1..]
  a = sum [x - y | (x, y) <- ys]
  b = sum [x^2 - y^2 | (x, y) <- ys]