Google – Next Number

Google – Next Number
Input一个string表示一个number, number不允许有重复的digit，返回满足要求的next number.
比如输入是789，返回790
比如输入是987，返回1023
[Solution]
Next Permutation的升级版。
从左到右扫一遍，mark用过的digit
从右到左扫，边扫边找比当前digit大且没有用过的digit，找到就break，否则就继续找。但注意在跳到下一个之前，要unmark当前的digit。

• break之后从break的位置开始用first missing number的方法generate后面的digit
• 如果扫到头都没有break，比如987就会是这样的情况，那就说明需要进一位。那么这种情况就是从头开始，generate一个n + 1位的number。

  public String nextNumber(String num) {

    if (num == null || num.isEmpty()) {

      return num;

    }

 

    int n = num.length();

    int[] map = new int[10];

    for (char c : num.toCharArray()) {

      map[c - '0'] = 1;

    }

 

    int i = 0;

    int next = -1;

    for (i = n - 1; i >= 0; i--) {

      int curr = num.charAt(i) - '0';

      next = curr + 1;

      while (next <= 9 && map[next] == 1) {

        next++;

      }

      map[curr] = 0;

      if (next <= 9) {

        break;

      }

    }

 

    StringBuilder sb = new StringBuilder();

    // 987 -> 1023

    if (i == -1) {

      sb.append("10");

      int d = 2;

      while (sb.length() < n + 1) {

        sb.append(d++);

      }

    }

    else {

      sb.append(num.substring(0, i));

      sb.append(next);

      map[next] = 1;

      next = 0;

      while (sb.length() < n) {

        while (next <= 9 && map[next] == 1) {

          next++;

        }

        sb.append(next);

        map[next] = 1;

      }

    }

 

    return sb.toString();

  }

Read full article from Google – Next Number