algorithm - 给定 K 个连续整数中的每一个的数字恢复序列

Question

记下从X开始的一系列N连续正整数。然后从每个数字中选择一个数字并以相同的顺序写入。我们需要找到满足数字系列的最小 X。

N 并且数字序列作为输入给出。我试图找到一些数学见解但失败了。 N 可以大到 10^5。

换句话说，给定一个包含数字的长度为N的数组A，我们需要找到一个长度为N的包含连续正整数(B[i+1] = B[i] + 1)的数组B，使得数字A [i] 可以在数字 B[i] 中找到，而 B[0] 是最小的。 (B 中没有数字包含前导 0)。

例如:如果给定 9、2、1、2、2，则最小的 X 为 19(19、20、21、22、23)。

另一个例子:如果给定 9 8 9 1 0 那么这样的序列将是 97 98 99 100 101。看到你可以在给定序列中的相应数字中找到这些数字。 97 是可能的最小起始数字(1097 也足够，但不是最小的)。

任何关于如何解决这个问题和这类问题的提示都会有所帮助。

Answer 1

这是一个O(N^2)-ish 算法，它可能不够好，也可能不够好，因为您没有链接原始问题，所以详细要求未知。

下面我假设 N = 100000。

For every y in [0, 100000):
    Consider the case that B[0] = 100000 * x + y for some x.
    This will be equivalent to requiring that x contains some of the digits in [0, 10),
    and that x + 1 contains some of the digits in [0, 10),
    from which a smallest x can easily be found (or pre-computed).
    (But the special case x = 0 needs further attention, problem of leading zero.)
Find the maximun of all 100000 * x + y found above, which is the answer.

有进一步的优化，具有类似的想法(例如，而不是查看最后五位数字，可以查看最后三位数字等)。但我现在不会发布这些详细信息。