在一个给定的字符串中找到缺失的数字。

Question

我发现了这个面试问题，经过深思熟虑，我并没有能够开发出一个可靠的算法。

给定一个连续数字的字符串，找出缺失的数字。数字范围未知。

样例输入："9899100101103104105"

答案：102

- Ankesh Anand

---

这是一个毫无意义的面试问题。 - Daniel Daranas

@DanielDanaras 我也是这么认为的。虽然不知道面试官的具体考察点是什么，但是看起来这确实是亚马逊的面试题。http://www.careercup.com/question?id=5564407157358592 - Ankesh Anand

如果你想要更高级一些，可以进行抽样来分析每个数字的频率。通过该分布，你应该能够在不到O(N)的时间内计算出间隔大小。 - Rusty Rob

@DanielDaranas 这个问题比许多其他问题要好得多。它具有足够的复杂性来测试能力（如果我们谈论实际实现，而不是基本思想），并且仅需要非常基本的数据结构和算法知识（你只需要两个for循环）（与许多其他问题不同，如果你了解某些特定的数据结构或算法，那么这些问题就很容易，否则就非常困难）。除非有更有效的解决方案，目前还没有人提到过特别详细的解决方案。 - Bernhard Barker

@DanielDaranas 唯一不会是“相当无意义”的事情就是解决一个尚未解决的问题，这在面试中期望太高了，除了那些不会出现的问题外，还有很多。因此，所有（/许多/大多数）面试问题都是“相当无意义”的，但它们存在的目的是为了测试能力。 - Bernhard Barker

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报告为缺失数字。

- Antti Huima

Answer 2

这里有一个可行的C#解决方案，你可以在LINQPad中检查：

void Main()
{
    FindMissingNumberInString("9899100101103104105").Dump("Should be 102");
    FindMissingNumberInString("78910121314").Dump("Should be 11");
    FindMissingNumberInString("99899910011002").Dump("Should be 1000");

    // will throw InvalidOperationException, we're missing both 1000 and 1002
    FindMissingNumberInString("99899910011003");
}

public static int FindMissingNumberInString(string s)
{
    for (int digits = 1; digits < 4; digits++)
    {
        int[] numbers = GetNumbersFromString(s, digits);
        int result;
        if (FindMissingNumber(numbers, out result))
            return result;
    }
    throw new InvalidOperationException("Unable to determine the missing number fro '" + s + "'");
}

public static int[] GetNumbersFromString(string s, int digits)
{
    var result = new List<int>();
    int index = digits;
    int number = int.Parse(s.Substring(0, digits));
    result.Add(number);

    while (index < s.Length)
    {
        string part;
        number++;
        digits = number.ToString().Length;
        if (s.Length - index < digits)
            part = s.Substring(index);
        else
            part = s.Substring(index, digits);
        result.Add(int.Parse(part));
        index += digits;
    }
    return result.ToArray();
}

public static bool FindMissingNumber(int[] numbers, out int missingNumber)
{
    missingNumber = 0;

    int? found = null;
    for (int index = 1; index < numbers.Length; index++)
    {
        switch (numbers[index] - numbers[index - 1])
        {
            case 1:
                // sequence continuing OK
                break;

            case 2:
                // gap we expect to occur once
                if (found == null)
                    found = numbers[index] - 1;
                else
                {
                    // occured twice
                    return false;
                }
                break;

            default:
                // not the right sequence
                return false;
        }
    }

    if (found.HasValue)
    {
        missingNumber = found.Value;
        return true;
    }

    return false;
}

这段代码可能可以大大简化，但在探索性编程时，我喜欢编写清晰易懂的代码，而不是试图用尽可能少的代码行或尽可能快地编写它。

- Lasse V. Karlsen

---

数字 < 4？“未给出数字范围”。 - Bernhard Barker

我知道，所以增加它，当我编写代码时只是一个简化。只要可以使用“int”来解析字符串，它就可以处理任意数量的数字。 - Lasse V. Karlsen

Answer 3

当然，唯一困难的部分是确定数字有多少位。我看到两种方法。

1. 尝试为第一个数字使用一定数量的数字，决定接下来的数字应该是什么（根据缺失的数字是第二个数字还是第三个数字，会有两个选项），然后查看是否与以下数字字符串匹配。如果匹配，则继续进行。如果字符串不符合模式，请尝试使用不同数量的数字再次尝试。
2. 查看字符串的起始和结束部分，并根据此和字符串的长度推断出数字的位数。这个方法有点含糊。

- Sneftel

Answer 4

1. digits=1
2. 解析字符串，第一个数字只包含digits个数字。
3. 解析下一个数字并检查它是否与上一个解析的数字是连续正确的。
4. 如果它减少了，digit+=1，回到1。
5. 如果它比上一个解析的数字高2，你可能找到了间隙，解析剩余部分，如果解析剩余部分不是递增序列，digit+=1，回到2，否则你已经找到了间隙。
6. 如果它比上一个解析的数字高1，回到3。
7. digit+=1，回到2。（我不确定这种情况是否会发生）

示例：
给定："131416"。
1. 数字=1
2. 解析 '1' 3. 解析 '3'
4. 它没有减少
5. 可能找到了间隙：解析剩余的 '1416' 失败，因为 '1' != '4'
=> 数字+=1 (数字=2) 转到 2
2. 解析 '13'
3. 解析 '14'
4. 它没有减少
5. 它不比上次解析的数（13）高2
6. 它比上次解析的数高1（14 = 13+1）=> 转到 3
3. 解析 '16'
4. 它没有减少
5. 可能找到了间隙：解析剩余的 '' 成功，因为没有更多的内容可解析，
=> 找到了间隙：'15' 是缺失的数字

- MrSmith42

---

我认为应该沿着这个方向思考，但是我觉得这并不正确。输入：“131416”。你的算法会输出2，而15才是正确答案。 - Ankesh Anand

我想我们需要加入更多的检查，例如当数字位数增加时会发生什么情况（从99到100）。我们正在考虑一个非常天真的解决方案，这可能有效，但我认为必须有一个更聪明的解决方案。 - Ankesh Anand

@Ankesh Anand：数字位数增加的情况很简单。我敢打赌，任何人都可以适应这种情况。可能会有一个“更聪明”的解决方案（无论你如何定义），但这个解决方案已经解决了问题（而这就是问题所在）。 - MrSmith42