如何从一串数字中找到缺少的数字,它们之间没有空格？

Question

输入格式

第一行将包含序列中的数字集.号码按升序列出.

边界条件

1 <= M <= 99999字符串S的长度为5至200.

输出格式

第一行将包含缺失的数字M.

输入/输出示例1

输入:12346789

输出:5

输入/输出2输入596597598600601602

输出:599

序列中的序列号为596 597 598 599 600 601 602. 599是缺失的数字

我的Java解决方案是:

我已经使用过split(("?<=\\G..."))等将数字分成一个,两个,三个四个和五个数字.并将数字保存到相应的数组中.然后我检查了数组中两个相邻数字之间的任何差异 - 如果它是一个那么它将调用一个函数来找到丢失的数字.

但问题在于:

输入:

999899991000110002 

输出:

10000

顺序是9998 9999 10001 10002.缺失的数字是10000

当从4位数转换为5位数时,如何拆分字符串？有没有更好的方法来解决这个问题？

public void test(Scanner in)
{
    String n = in.nextLine();
    int n1 = n.length();
    System.out.println(n1);
    if (n1 % 2 == 0)
    {

    } else {
      n = "0" + n;
    }
    System.out.println(n);
    String[] one = n.split("(?<=\\G.)");
    String[] two = n.split("(?<=\\G..)");
    String[] three = n.split("(?<=\\G...)");
    String[] four = n.split("(?<=\\G....)");
    String[] five = n.split("(?<=\\G.....)");
    int x = one.length;
    int y = two.length;
    int z = three.length;
    int u = four.length;
    int v = five.length;
    int[] aa1 = new int [x];
    int[] aa2 = new int [y];
    int[] aa3 = new int [z];
    int[] aa4 = new int [u];
    int[] aa5 = new int [v];
    for (int i = 0; i < x; i++)
    {
        aa1[i] = Integer.parseInt(one[i]);
    }
    if (aa1[1] == aa1[3] - 2)
    {
        findmissing(aa1, x);          
    }
    for (int i = 0; i < y; i++)
    {
        aa2[i] = Integer.parseInt(two[i]);
    }
    if (aa2[1] == aa2[3] - 2)
    {
        findmissing(aa2, y);
    }
    for (int i = 0; i < z; i++)
    {
        aa3[i] = Integer.parseInt(three[i]);
    }
    if (aa3[1] == aa3[3] - 2)
    {
        findmissing(aa3, z);
    }
    for (int i = 0; i < u; i++)
    {
        aa4[i] = Integer.parseInt(four[i]);
    }
    if (aa4[1] == aa4[3] - 2)
    {
        findmissing(aa4, u);
    }
    for (int i = 0; i < v; i++)
    {
        aa5[i] = Integer.parseInt(five[i]);
    }
    if (aa5[1] == aa5[3] - 2)
    {
        findmissing(aa5, v);
    }
    in.close();
}

public static void findmissing(int[] bb, int value)
{
    for (int i = 0; i < value - 1; i++)
    {
        if (bb[i] == bb[i + 1] - 1)
        {

        } else {
            System.out.println(bb[i + 1] - 1);
        }
    }
}

Answer 1

如果（正如我假设的那样）数字按顺序列出，那么一个非常简单的算法将起作用：

• 对于第一个数字的每个可能的数字长度 1 <= d <= 5：
  • 调用try(toInt(S[1 .. d]), S[d+1 .. |S|])以尝试以 S[1 .. d] 编码的数字开头的数字序列。如果该序列“有效”，则输出它并停止。

上面的主循环在 d = 5 处停止，因为您给出了 M <= 99999 的约束，但它可以轻松地处理任意大的数字，只需让 d 一直增加到 |S| 即可。

第二步（“尝试...”）很简单，因为您已经拥有此（候选）序列中的第一个数字 x，因此您可以轻松生成与下一个应该出现的数字相对应的数字字符串（即对应的x+1）并与S的其余部分进行比较。如果x+1对应的数字串与S的前几个字符不匹配，则尝试x+2对应的数字串。如果匹配，则设置一个标志，记录 x+1 可能是丢失的数字这一事实，然后继续。如果 x+1 和 x+2 都不匹配，或者如果 x+1 不匹配并且标志已经设置，我们知道初始值不可能是正确的，因此返回并让主循环尝试下一个更长的初始值:

try(x, S):
    x1str = asString(x + 1)
    x2str = asString(x + 2)
    missing = -1        # Flag value to indicate "not found"
    while |S| >= |x1str|:
        if S[1 .. |x1str|] = x1str:
            Delete first |x1str| characters of S
            x = x + 1
            x1str = asString(x + 1)
            x2str = asString(x + 2)
        else if S[1 .. |x2str|] = x2str and missing = -1:
            Delete first |x2str| characters of S
            missing = x + 1
            x = x + 2
            x1str = asString(x + 1)
            x2str = asString(x + 2)
        else
            return -1    # Flag value to indicate "invalid sequence"
    if |S| > 0 then return -1    # Some gunk was left over
    return missing

显然，您可以仅使用（不变的）字符串中的偏移量来替换“删除 S 的第一个...字符”步骤，但我觉得上面的解释更容易。