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

Question

我发现这个面试问题四处游荡，经过深思熟虑，我无法真正为它开发出合理的算法。

给定一串按顺序排列的数字，找到缺失的数字。数字的范围没有给出。

示例输入：“9899100101103104105”

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

Answer 2

1. digits=1
2. 解析字符串，就像第一个digits数字只包含数字一样。
3. 解析下一个数字并检查它是否与最后一个解析的数字相关的顺序正确
4. 如果它减少，digit+=1，转到 1。
5. 如果它比上次解析的高2，则可能找到间隙，解析其余部分，如果解析的其余部分不是递增序列，digit+=1则转到2，否则您已找到间隙。
6. 如果它比上次解析的数字高 1，则转到 3。
7. digit+=1，转到2。（我不确定这种情况是否会发生）

示例：
给定：“131416”。
1.digits=1
2.解析'1' 3.解析'3'
4.不减
5.可能发现差距：解析其余的'1416'失败，因为'1' != '4'
=> digit+ =1 (digit=2) goto 2
2. parse '13'
3. parse '14'
4. 它不减少
5. 它不比最后解析的一 (13) 高 2
6. 它高 1 (14 = 13+1) => goto 3
3. 解析 '16'
4. 它没有减少
5. 可能找到了差距：解析剩下的 '' 因为没有什么要解析了，
=> 找到了 gab: '15' 是丢失的号码

Answer 3

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

1. 为第一个数字尝试一定数量的数字，然后决定接下来的数字应该是什么（将有两个选项，取决于缺少的数字是否是第二个数字），并查看它是否与以下数字字符串匹配。如果是这样，请继续。如果字符串不符合模式，请使用不同的位数重试。
2. 查看字符串的开头和结尾部分，并根据该部分和字符串的长度推断位数。这个有点手摇。

Answer 4

这是一个可用的 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;
}

这可能会大大简化，但在探索性编码期间，我喜欢写出清晰易懂的代码，而不是尝试用尽可能少的代码行或尽可能快的速度编写它。