java - 如何从一串数字之间没有空格的数字中找到缺失的数字？

Question

Input Format

The first line will contain the set of numbers in the sequence. Number are listed in ascending order.

Boundary Conditions

1<=M<=99999 Length of string S is from 5 to 200.

Output Format

The first line will contain the missing number M.

Example Input /Output 1

Input: 12346789

Output: 5

Input /Output 2 Input 596597598600601602

Output : 599

The numbers a sequence in the sequence are 596 597 598 599 600 601 602. 599 is the missing numbers

我的 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 的第一个 ... 字符”步骤替换为仅在(不变的)字符串中使用一个偏移量，但我觉得上面的解释更容易理解。