javascript - 如何在范围内的随机非重复整数字符串中找到丢失的整数

Question

我什至开始思考如何做到这一点都遇到了麻烦。

我需要在一串没有分隔符的随机数中找到一个缺失的数字。

这是一个示例:14036587109。在这个例子中，缺失的数字是2，范围是0-10(含)。

如何编写 JavaScript/Node.JS 程序来解决这个问题？

我无法弄清楚的部分是程序如何分隔数字；在上面的示例中，程序如何知道数字 10(在最后一个数字之前)不是数字 1 和 0。

Answer 1

关于缺失整数，我们知道两件事:输入中的总位数告诉我们缺失整数中的位数，以及(如@samgak 在评论中提到的那样)计算每个数字在输入告诉我们丢失的整数是由哪些数字组成的。如果输入中缺少这些数字的排列之一，这可能会为我们提供解决方案的快速路径。如果没有，则:

找出从最高位数到最低位数的整数；如果范围是例如0-999，则先查找3位整数，再查找2，再查找1。

如果整数仅出现在输入中的一个位置，则将其标记为已找到，并将其从输入中删除。

然后，再次从尚未找到的最长整数开始，查看出现在两个位置的整数；尝试这两个选项，然后检查是否还存在依赖于我们使用的数字的所有其他整数；例如如果 357 出现在两个位置:

... 1235789 ... 2435768 ...
      357         357
     23          43
    123         243
     235         435
       578         576
        78          76
        789         768

当尝试 357 的第一个位置时，检查 23、123、235、578、78 和 789 是否还有其他可能性。对于第二个位置，检查 43、243、435、576、76 和 768。

如果这些检查显示只有一个选项是可能的，则将数字标记为已找到并将其从输入中删除。

继续对较短的整数以及出现在 3、4、... 位置的整数执行此操作。如果这样做到一定程度，还是没有结果，你可能要递归地尝试几个选项，这会很快导致选项数量巨大。 (使用特别设计的大输入，可能会阻止此方法并使其慢得无法使用。)但随机输入的平均复杂度可能还不错。

---

实际上，当您发现一个整数只出现在输入的一个位置，但它是缺失数字的排列时，您不应该删除它，因为它可能是缺失的整数。所以算法可能是:删除所有你可以在输入中明确定位的整数，然后尝试一个一个地删除所有可能丢失的整数，并寻找不一致之处，即其他没有正确长度或数字的丢失数字。

---

当然，这完全是一个启发式问题。你尝试一些简单的东西，如果这不起作用，你尝试更复杂的东西，如果那不起作用，你尝试更复杂的东西......在每一步都有几个选项，每个选项都可能是某些人的最佳选择输入字符串但不输入其他字符串。

例如如果范围是 0-5000，则首先标记仅出现在一个位置的 4 位整数。但在那之后，你可以再次做同样的事情(因为出现两次的整数可能已经删除了它们的一个选项)直到没有更多的改进，或者你可以检查出现两次的整数，或者出现最多的整数x 次，或者转向 3 位整数……我认为没有一种直接的方法可以知道这些选项中的哪一个会给出最好的结果。