如何在没有空格的数字字符串中找到一个缺失的数字？

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..."))等方法，把数字分成一位、两位、三位、四位和五位，然后把这些数字保存到相应的数组中。接着，我检查数组中任意两个相邻数字之间是否差为1，如果是，则调用一个函数来查找缺失的数字。

但问题是当：

输入：

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);
        }
    }
}

- dmj

---

例子1似乎有问题。输入不应该缺少5吗？否则这是一个有趣的逻辑问题。我敢打赌，如果你在纸上多做一些练习，你会得出一个不错的解决方案。我有一种隐隐的感觉，你能胜任这个任务。如果这是我的任务，我会在纸上列出像你上面描述的典型边缘情况的示例，从最简单的单个数字情况到更大的数字情况。 - Hovercraft Full Of Eels

编写自己的分割函数是正确的方法。在这里，您可以根据需要修改数字的数量。 - Bernhard Barker

我假设这些数字是按顺序列出的？你并没有明确说明。 - j_random_hacker

也许你可以尝试一次只读取一个数字，而不是立即将所有数字加载到数组中。然后，你就会知道下一个期望的数字是什么，以及你需要多少个字符。你需要重新构建很多代码，但它可能有助于处理这些边缘情况。例如：读取998，下一个期望的数字是999，因此读取3个字符并检查，然后数字是999，下一个期望的数字是1000，所以读取4个字符并检查。但这假设你知道第一个数字，我不知道是否总是这种情况。 - JustWannaFly

@jdkorv11：你和我基本上有相同的想法。要处理不知道第一个数字其实很容易：只需尝试它们全部！ :) - j_random_hacker

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的前...个字符”步骤，但我觉得上述方法更容易解释。

- j_random_hacker

Answer 2

这是一个递归的可运行解决方案。

public class FindGaps {
  public static void main(String... args) throws Exception {
    System.out.println(gapFinder("12345789"));//6 expected
    System.out.println(gapFinder("99101"));//100 expected
    System.out.println(gapFinder("124126"));//123 expected
    System.out.println("fail expected: " + gapFinder("124125"));
    System.out.println("fail expected: " + gapFinder("123456A8"));
    System.out.println("fail expected: " + gapFinder("9910010210"));
    System.out.println("fail expected: " + gapFinder("10121416"));
  }

  public static int gapFinder(final String sequence) throws Exception {
    for (int digits = 1; digits <= sequence.length() / 2; digits++) {
      final Integer currentNumber = Integer.parseInt(sequence.substring(0, digits));
      final Integer ret = recursiveGapChecker(currentNumber + 1, sequence.substring(digits));
      if (ret != null && ret >= 0) {
        return ret;
      }
    }
    return -1;
  }

  /**
   * @return null if the sequence is validated, the missing number if a gap is found, return<0 if the sequence is invalid
   */
  private static Integer recursiveGapChecker(final Integer nextNumber, final String remainder) {
    final String numAsString = nextNumber.toString();
    final int numLength = numAsString.length();
    final Integer numPlus1 = nextNumber + 1;
    final String numPlus1AsString = numPlus1.toString();
    final int numPlus1Length = numPlus1AsString.length();
    if (remainder.isEmpty()) {
      return null;//cleanly parsed the remainer
    } else if (remainder.length() < numLength) {
      return -1;//invalid length
    } else if (remainder.startsWith(numAsString)) {
      return recursiveGapChecker(nextNumber + 1, remainder.substring(numLength));
    } else if (remainder.startsWith(numPlus1AsString)) {
      Integer ret = recursiveGapChecker(numPlus1 + 1, remainder.substring(numPlus1Length));
      if (ret == null) {
        return nextNumber;//found it!
      } else if (ret < 0) {
        return -1;//problem parsing the rest of the string
      } else {
        return -2;//found more than one gap
      }
    } else {
      return -1;//the remainder doesn't match the given number
    }
  }
}

- Andreas

---

这基本上是我的解决方案，但迭代被递归所替代。 - j_random_hacker

Answer 3

如果您已经知道要期望的第一个数字，那么这应该可以工作。不过，确定第一个数字可能会有些棘手。

public class SeqTest
{
    public static void main(String[] args)
    {
        new SeqTest().test("999899991000110002", 9998);
        System.exit(0);
    }

    public void test(String line, int nextExpectedNumber)
    {
        String remainingLine = line;
        boolean expected = true;
        Integer nextNumber = nextExpectedNumber;

        while (expected)
        {
            String expectedString = nextNumber.toString();

            if (!remainingLine.startsWith(expectedString))
            {
                expected = false;
                System.out.println("Missing " + expectedString + " from " + remainingLine);
            } else {
                // prune remainingLine
                remainingLine = remainingLine.substring(expectedString.length());
            }
            nextNumber = this.nextInSequence(nextNumber);
        }

        return;
    }

    public Integer nextInSequence(int current)
    {
        return ++current;
    }
}

- Parker

Answer 4

除了解决 OP 给出的问题，您还需要解决两个附加问题。

1. 当数字从长度变为长度+1时会发生什么？
2. 当您有一个初始数对，它们也适用于较短的长度，例如 9899 和 9900 时，会发生什么？您可以将这些数字检测为 98、99、99、00。

无论如何，这里是我针对我的代码运行的测试用例。第一行是数字字符串。第二行是来自字符串的数字数组。第三行是缺失的数字。

1234678910
[1, 2, 3, 4, 6, 7, 8, 9, 10]
5

26272829313233
[26, 27, 28, 29, 31, 32, 33]
30

9293949596979899101
[92, 93, 94, 95, 96, 97, 98, 99, 101]
100

99101102103104105106107108109110111112
[99, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112]
100

596597598600601602
[596, 597, 598, 600, 601, 602]
599

989999009901990299049905
[9899, 9900, 9901, 9902, 9904, 9905]
9903

98999901990299039904990599069907
[9899, 9901, 9902, 9903, 9904, 9905, 9906, 9907]
9900

9998999910000100011000210004
[9998, 9999, 10000, 10001, 10002, 10004]
10003

这段代码所要表达的意思是要尽可能想到所有边缘情况进行测试。如果我没有编写过这段代码，我就不会想到 9899、9900 这个序列。

package com.ggl.testing;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class MissingNumber implements Runnable {

    private String numberString;

    public static void main(String[] args) {
        MissingNumber missingNumber = new MissingNumber();
        missingNumber.setNumberString("1234678910");
        missingNumber.run();
        missingNumber.setNumberString("26272829313233");
        missingNumber.run();
        missingNumber.setNumberString("9293949596979899101");
        missingNumber.run();
        missingNumber.setNumberString("99101102103104105106107108109110111112");
        missingNumber.run();
        missingNumber.setNumberString("596597598600601602");
        missingNumber.run();
        missingNumber.setNumberString("989999009901990299049905");
        missingNumber.run();
        missingNumber.setNumberString("98999901990299039904990599069907");
        missingNumber.run();
        missingNumber.setNumberString("9998999910000100011000210004");
        missingNumber.run();
    }

    public void setNumberString(String numberString) {
        this.numberString = numberString;
    }

    @Override
    public void run() {
        System.out.println(numberString);
        Integer[] numbers = getNumbers(numberString);
        System.out.println(Arrays.toString(numbers));
        int missingNumber = findMissingNumber(numbers);
        System.out.println(missingNumber + "\n");
    }

    private Integer[] getNumbers(String numberString) {
        List<Integer> numbers = new ArrayList<>();
        int index1 = 0;
        int index2 = 1;
        int length = 1;
        boolean isAdjacent = false;

        while (!isAdjacent) {
            Integer test1 = getSubstring(numberString, index1, length);
            Integer test2 = getSubstring(numberString, index2, length);
            Integer test3 = getSubstring(numberString, index2, length + 1);
            if (isValidDifference(test2, test1)) {
                numbers.add(test1);
                numbers.add(test2);
                try {
                    getRemainingNumbers(numberString, numbers, index2, length,
                            test2);
                    isAdjacent = true;
                } catch (NumberFormatException e) {
                    numbers.clear();
                    length++;
                    index1 = 0;
                    index2 = index1 + length;
                }
            } else if (isValidDifference(test3, test1)) {
                numbers.add(test1);
                numbers.add(test3);
                length++;
                try {
                    getRemainingNumbers(numberString, numbers, index2, length,
                            test3);
                    isAdjacent = true;
                } catch (NumberFormatException e) {
                    numbers.clear();
                    length++;
                    index1 = 0;
                    index2 = index1 + length;
                }
            } else {
                length++;
                index2 = index1 + length;
            }
        }

        return numbers.toArray(new Integer[numbers.size()]);
    }

    private void getRemainingNumbers(String numberString,
            List<Integer> numbers, int index2, int length, Integer previousTest)
            throws NumberFormatException {
        int index = index2 + length;
        while (index <= (numberString.length() - length)) {
            Integer test = getSubstring(numberString, index, length);
            if (isValidDifference(test, previousTest)) {
                numbers.add(test);
                previousTest = test;
                index += length;
            } else {
                length++;
            }
        }
    }

    private Integer getSubstring(String string, int index, int length)
            throws NumberFormatException {
        return Integer.valueOf(string.substring(index, index + length));
    }

    private boolean isValidDifference(int number2, int number1) {
        int diff = number2 - number1;
        return (diff == 1 || diff == 2);
    }

    private int findMissingNumber(Integer[] numbers) {
        int lastNumber = numbers[0];
        for (int i = 1; i < numbers.length; i++) {
            int diff = numbers[i] - lastNumber;
            if (diff == 2) {
                return numbers[i] - 1;
            }
            lastNumber = numbers[i];
        }

        return Integer.MIN_VALUE;
    }

}

- Gilbert Le Blanc

Answer 5

我认为你可以改进这段代码，但是尝试一下：

public static void main(String[] args) {
    String pattern = "(\\d{%s})(\\d{0,%s})";
    String toVerify = "9979989991000100110021004";
    String toVerifyCopy = toVerify;

    List<Integer> items = new LinkedList<>();

    Integer found = null;

    for (int i = 1; i < toVerifyCopy.length(); i++) {
        int first = 0;
        Integer second = 0;

        int secondSize = i;
        boolean isSize = false;

        for (int j = 1; j < i + 2; j++) {
            Pattern patron = Pattern.compile(String.format(pattern, i, j));

            Matcher matcher = patron.matcher(toVerifyCopy);

            if (matcher.find()) {
                first = Integer.parseInt(matcher.group(1));
                second = Integer.parseInt(matcher.group(2));

                if (second == first + 1) {
                    secondSize = j;
                    isSize = true;

                    j++;
                } else if (second == first + 2) {
                    found = first + 1;
                    secondSize = j;

                    isSize = true;
                    j++;
                } else {
                    isSize = false;
                }
            }
        }

        if (isSize) {
            toVerifyCopy = toVerifyCopy.substring(i);
            i = i - 1;

            if (items.size() < 2 ||
                toVerifyCopy.length() == i + secondSize) {
                items.add(first);
            }

            items.add(second);
        } else {
            if (items.size() > 0) {
                if (first == items.get(items.size() - 1)) {
                    items.clear();

                    toVerifyCopy = toVerify;
                }
            }
        }
    }

    for (Integer item : items) {
        System.out.println(item);
    }

    if (found != null) {
        System.out.println("Found: " + found);
    }
}

- maframaran

Answer 6

for a sequence, (3, 4, 6, 7) 
or              (13, 14, 16, 17) 
or              (113, 114, 116, 117) 

你最终会得到 last-first == sequence.size()，即 7-3 = 4。

这样，就容易检测出正确的数字长度（至少可以显著减少要检查的数字列表）。

为了提高性能，你可以检查 String.length 是否可被数字长度整除，否则可能会遇到以下问题：

如果你只选择第一个和最后一个字符来测试数字长度为 3，则会出现 1230124 的问题。

import java.util.*;

public class NumberGap {

    static private boolean laengeFits (String numbers, int len, int start, int stop) {
        String front = numbers.substring (start, len);
        String back  = numbers.substring (stop - len, stop);
        // System.out.printf ("front - back = %s %s\n", front, back);
        int first = Integer.parseInt (front);
        int last  = Integer.parseInt (back);
        return (last - first == numbers.length () / len);
    }

    static private boolean isCandidate (String numbers, int len) {
        return (numbers.length() % len == 0 && laengeFits (numbers, len, 0, numbers.length ()));
    }

    static List <Integer> string2ints (String snum, int i) {
        List <Integer> vals = new ArrayList<> ();
        for (int n = 0; n < snum.length (); n+= i){
             String s = snum.substring (n, n+i);
             vals.add (Integer.parseInt (s));
        }
        return vals;
    }

    static private void findGap (String numbers) {
        System.out.printf ("\nSearching for: %s \n", numbers);
        for (int i = 1; i < 6; ++i) {
            if (isCandidate (numbers, i)) {
                List <Integer> vals = string2ints (numbers, i);
                // System.out.printf ("\telems: %d :\n", vals.size ());
                List <Integer> res = new ArrayList<> ();
                for (int j = 1; j < vals.size (); ++j) {
                    if (vals.get(j) != vals.get(j-1) + 1) {
                        res.add (vals.get(j-1) + 1);
                        if (res.size () > 1) {
                           System.out.printf ("Error multiple gaps: %d %d\n", res.get (0), res.get(1));
                           break;
                        }
                    }
                }
                if (res.size() == 1) {
                    System.out.printf (" * * *   Gap: %d   * * *\n", res.get (0));
                    continue;
                }
            }
        }
    }

    public static void main(String[] args) {
        findGap ("012346789");
        findGap ("1234678910");
        findGap ("26272829313233");
        findGap ("26272829313333");
        findGap ("9293949596979899101");
        findGap ("99101102103104105106107108109110111112");
        findGap ("596597598600601602");
        findGap ("989999009901990299049905");
        findGap ("98999901990299039904990599069907");
        findGap ("9998999910000100011000210004");
    }
}

我最初写了一个Scala解决方案，一行代码搞定，尽管这是一行相当长的代码：

(1 to 5).map (i => {s.sliding (i, i)}.map (_.toInt).toVector).filter (v => (v(v.size - 1) - v(0) == v.size)).flatten .sliding (2, 1).filter {l => l(0) != l(1)-1}.map {l => l(1) -1}.mkString (":")

或者更易读：

(1 to 5).map (i => {s.sliding (i, i)}.
    map (_.toInt).toVector).
    filter (v => (v(v.size - 1) - v(0) == v.size)).
    flatten.
    sliding (2, 1).
    filter {l => l(0) != l(1)-1}.
    map {l => l(1) -1}.mkString (":")

假设s是要解析的字符串。集合函数的集合更加丰富，不需要将数组转换为列表或向量，因为这里只定义了一个方便的函数，而其他函数则在其他地方定义。在幕后流畅地将int转换为Integer。

- user unknown