string - 查找给定字符串中缺失的数字

Question

我发现这个面试问题飘来飘去，想了很多，我无法真正为它开发一个合理的算法。

Given a string of numbers in sequential order, find the missing number.The range of numbers is not given.

Sample Input:"9899100101103104105"

Answer:102

Answer 1

这是一个简单的问题。

1. 猜猜第一个数字的位数
2. 一个一个地从字符串中读取数字。如果你读到的前一个数字是 x，那么下一个数字必须是 x + 1 或 x + 2。如果是 x + 2，记住 x + 1 是错过的数字，继续直到字符串的末尾以验证最初的猜测是正确的。如果您读到 x + 1 或 x + 2 以外的内容，则最初的猜测是错误的，您需要重新开始(下一个)猜测。

以你的例子:

9899100101103104105

第一次猜测长度1

read 9
the next number should be either 10 or 11. Read the next two digits, you get 89.
That is incorrect, so the initial guess was wrong.

第二次猜测长度2

read 98
the next number should be either 99 or 100. Read the next two digits for 99
the next number should be either 100 or 101. Read the next three digits for 100
... 101
... 103 (remember 102 as the missed number)
... 104
... 105
end of input

长度为 2 的猜测被验证为正确猜测，102 被报告为缺失数字。