Question

2048. 下一个更大的数值平衡数

English Version

题目描述

如果整数  x 满足：对于每个数位 d ，这个数位 恰好 在 x 中出现 d 次。那么整数 x 就是一个 数值平衡数 。

给你一个整数 n ，请你返回 严格大于 n 的 最小数值平衡数 。

 

示例 1：

输入：n = 1
输出：22
解释：
22 是一个数值平衡数，因为：
- 数字 2 出现 2 次 
这也是严格大于 1 的最小数值平衡数。

示例 2：

输入：n = 1000
输出：1333
解释：
1333 是一个数值平衡数，因为：
- 数字 1 出现 1 次。
- 数字 3 出现 3 次。 
这也是严格大于 1000 的最小数值平衡数。
注意，1022 不能作为本输入的答案，因为数字 0 的出现次数超过了 0 。

示例 3：

输入：n = 3000
输出：3133
解释：
3133 是一个数值平衡数，因为：
- 数字 1 出现 1 次。
- 数字 3 出现 3 次。 
这也是严格大于 3000 的最小数值平衡数。

 

提示：

• 0 <= n <= 106

解法

方法一：枚举

我们注意到，题目中 $n$ 的范围是 $[0, 10^6]$，而大于 $10^6$ 的其中一个数值平衡数是 $1224444$，因此我们直接枚举 $x \in [n + 1, ..]$，然后判断 $x$ 是否是数值平衡数即可。枚举的 $x$ 一定不会超过 $1224444$。

时间复杂度 $O(M - n)$，其中 $M = 1224444$。空间复杂度 $O(1)$。

class Solution:
  def nextBeautifulNumber(self, n: int) -> int:
    for x in count(n + 1):
      y = x
      cnt = [0] * 10
      while y:
        y, v = divmod(y, 10)
        cnt[v] += 1
      if all(v == 0 or i == v for i, v in enumerate(cnt)):
        return x

class Solution {
  public int nextBeautifulNumber(int n) {
    for (int x = n + 1;; ++x) {
      int[] cnt = new int[10];
      for (int y = x; y > 0; y /= 10) {
        ++cnt[y % 10];
      }
      boolean ok = true;
      for (int y = x; y > 0; y /= 10) {
        if (y % 10 != cnt[y % 10]) {
          ok = false;
          break;
        }
      }
      if (ok) {
        return x;
      }
    }
  }
}

class Solution {
public:
  int nextBeautifulNumber(int n) {
    for (int x = n + 1;; ++x) {
      int cnt[10]{};
      for (int y = x; y > 0; y /= 10) {
        ++cnt[y % 10];
      }
      bool ok = true;
      for (int y = x; y > 0; y /= 10) {
        if (y % 10 != cnt[y % 10]) {
          ok = false;
          break;
        }
      }
      if (ok) {
        return x;
      }
    }
  }
};

func nextBeautifulNumber(n int) int {
  for x := n + 1; ; x++ {
    cnt := [10]int{}
    for y := x; y > 0; y /= 10 {
      cnt[y%10]++
    }
    ok := true
    for y := x; y > 0; y /= 10 {
      if y%10 != cnt[y%10] {
        ok = false
        break
      }
    }
    if ok {
      return x
    }
  }
}

function nextBeautifulNumber(n: number): number {
  for (let x = n + 1; ; ++x) {
    const cnt: number[] = Array(10).fill(0);
    for (let y = x; y > 0; y = (y / 10) | 0) {
      cnt[y % 10]++;
    }
    let ok = true;
    for (let i = 0; i < 10; ++i) {
      if (cnt[i] && cnt[i] !== i) {
        ok = false;
        break;
      }
    }
    if (ok) {
      return x;
    }
  }
}