下一个更大的数值平衡数 图解题解

这道题到底在问什么

输入

n = 1

输出

22(数位 2 出现 2 次)

输入

n = 1000

输出

1333(1 出现 1 次,3 出现 3 次)

输入

n = 13

输出

22(本节演示用例)

先想最直接的笨办法

记牢这一句:从 n 的下一个数开始,挨个试。判定一个数平不平衡,就看它每个数位 d 是不是恰好出现 d 次。下面从 14 开始,一步一步试到 22。（动画第 3 步）

最优解：一步一步想明白

1. 3记牢这一句:从 n 的下一个数开始,挨个试。判定一个数平不平衡,就看它每个数位 d 是不是恰好出现 d 次。下面从 14 开始,一步一步试到 22。
2. 4枚举起点 14这一排就是我们要挨个验的候选,从 n 加 1 也就是 14 开始,一直往上。算法很朴素:排头这个先试,不平衡就划掉换下一个,直到撞上第一个平衡数。紫色高亮的就是当前正在试的候选,现在轮到 14。
3. 5统计 14 的数位轮到候选 14。先把它拆成一个个数位,每碰到一个数位就在计数桶 cnt 里给对应的格子加一。14 拆出来是 1 和 4,统计下来 数位 1 出现 1 次,数位 4 出现 1 次。侧栏这张小表就是 cnt,记录了每个出现过的数位各出现了几次。
4. 614 淘汰判定 14。数位 1 那一位是对上了,数位 4 出现 1 次,却需要出现 4 次,这一位对不上,整个数就不平衡。把 14 划掉,枚举指针往前挪一格,去试 15。
5. 7统计 15 的数位轮到候选 15。先把它拆成一个个数位,每碰到一个数位就在计数桶 cnt 里给对应的格子加一。15 拆出来是 1 和 5,统计下来 数位 1 出现 1 次,数位 5 出现 1 次。侧栏这张小表就是 cnt,记录了每个出现过的数位各出现了几次。
6. 815 淘汰判定 15。数位 1 那一位是对上了,数位 5 出现 1 次,却需要出现 5 次,这一位对不上,整个数就不平衡。把 15 划掉,枚举指针往前挪一格,去试 16。
7. 9统计 16 的数位轮到候选 16。先把它拆成一个个数位,每碰到一个数位就在计数桶 cnt 里给对应的格子加一。16 拆出来是 1 和 6,统计下来 数位 1 出现 1 次,数位 6 出现 1 次。侧栏这张小表就是 cnt,记录了每个出现过的数位各出现了几次。
8. 1016 淘汰判定 16。数位 1 那一位是对上了,数位 6 出现 1 次,却需要出现 6 次,这一位对不上,整个数就不平衡。把 16 划掉,枚举指针往前挪一格,去试 17。
9. 11统计 17 的数位轮到候选 17。先把它拆成一个个数位,每碰到一个数位就在计数桶 cnt 里给对应的格子加一。17 拆出来是 1 和 7,统计下来 数位 1 出现 1 次,数位 7 出现 1 次。侧栏这张小表就是 cnt,记录了每个出现过的数位各出现了几次。
10. 1217 淘汰判定 17。数位 1 那一位是对上了,数位 7 出现 1 次,却需要出现 7 次,这一位对不上,整个数就不平衡。把 17 划掉,枚举指针往前挪一格,去试 18。
11. 13统计 18 的数位轮到候选 18。先把它拆成一个个数位,每碰到一个数位就在计数桶 cnt 里给对应的格子加一。18 拆出来是 1 和 8,统计下来 数位 1 出现 1 次,数位 8 出现 1 次。侧栏这张小表就是 cnt,记录了每个出现过的数位各出现了几次。
12. 1418 淘汰判定 18。数位 1 那一位是对上了,数位 8 出现 1 次,却需要出现 8 次,这一位对不上,整个数就不平衡。把 18 划掉,枚举指针往前挪一格,去试 19。
13. 15统计 19 的数位轮到候选 19。先把它拆成一个个数位,每碰到一个数位就在计数桶 cnt 里给对应的格子加一。19 拆出来是 1 和 9,统计下来 数位 1 出现 1 次,数位 9 出现 1 次。侧栏这张小表就是 cnt,记录了每个出现过的数位各出现了几次。
14. 1619 淘汰判定 19。数位 1 那一位是对上了,数位 9 出现 1 次,却需要出现 9 次,这一位对不上,整个数就不平衡。把 19 划掉,枚举指针往前挪一格,去试 20。
15. 17已淘汰 14-19试到这里停一下看看进度。14 到 19 这六个已经全被划成灰色,它们淘汰的原因其实一模一样:除了数位 1 是出现 1 次刚好达标,另一个数位比如 4 到 9,都只出现了 1 次,可它们要求出现自己那么多次,次数远远不够。接着往下,轮到 20,这个数里藏着 0,会更干脆地出局。
16. 18统计 20 的数位轮到候选 20。先把它拆成一个个数位,每碰到一个数位就在计数桶 cnt 里给对应的格子加一。20 拆出来是 2 和 0,统计下来 数位 0 出现 1 次,数位 2 出现 1 次。侧栏这张小表就是 cnt,记录了每个出现过的数位各出现了几次。
17. 1920 淘汰判定 20。数位 2 出现 1 次,却需要出现 2 次,这一位对不上,整个数就不平衡。注意数位 0:它一出现就必然违规,因为平衡数要求 0 出现 0 次,自相矛盾。把 20 划掉,枚举指针往前挪一格,去试 21。
18. 20统计 21 的数位轮到候选 21。先把它拆成一个个数位,每碰到一个数位就在计数桶 cnt 里给对应的格子加一。21 拆出来是 2 和 1,统计下来 数位 1 出现 1 次,数位 2 出现 1 次。侧栏这张小表就是 cnt,记录了每个出现过的数位各出现了几次。
19. 2121 淘汰判定 21。数位 1 那一位是对上了,数位 2 出现 1 次,却需要出现 2 次,这一位对不上,整个数就不平衡。把 21 划掉,枚举指针往前挪一格,去试 22。
20. 22统计 22 的数位轮到候选 22。先把它拆成一个个数位,每碰到一个数位就在计数桶 cnt 里给对应的格子加一。22 拆出来是 2 和 2,统计下来 数位 2 出现 2 次。侧栏这张小表就是 cnt,记录了每个出现过的数位各出现了几次。
21. 2322 命中判定 22。它只有数位 2,而 2 恰好出现 2 次,cnt[2] 等于 2,完全配平。这是我们从 14 一路试上来,第一个满足条件的数。算法在这里立刻停手,把 22 返回,它就是严格大于 13 的最小平衡数。
22. 2422 复核通过再复核一眼,确认没漏判。cnt 这张表里只有数位 2 亮着,值是 2,其余从 0 到 9 的格子全是 0,没有任何出现了却次数对不上的数位,也没有 0 来捣乱。条件干干净净地满足,答案就锁定在 22。
23. 25答案 = 22回看整排候选。14 到 21 这八个,要么某个数位次数不够,要么含了 0,全被划成灰色淘汰掉;只有排在最后的 22 一路配平,亮成绿色。枚举从 14 走到 22,撞上第一个平衡数就返回,答案就是 22,和一开始说的对上了。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
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

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
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;
            }
        }
    }
};

import java.util.*;
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;
            }
        }
    }
}

复杂度

面试官可能追问