给定来自K个连续整数的每个数字的数字恢复序列

Question

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

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

换句话说,给定和包含数字的长度为N的数组A,我们需要找到包含连续正整数(B [i + 1] = B [i] + 1)的长度为N的数组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.

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