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

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

力扣题目链接：https://leetcode.cn/problems/next-greater-numerically-balanced-number/

如果整数 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 <= 10⁶

方法一：枚举

我们可以很方便地写一个函数用来判断一个数 $n$ 是否为“数值平衡数”。

只需要取出这个数的每一位并统计出现次数，从0到10遍历，如果出现次数不等于这个数就返回false，否则返回true。

接下来从给定的 $n$ 的下一个数开始枚举，直到枚举到了“数值平衡数”为止。

时间复杂度：不易计算，但是能过（方法二中也可以看出无论给定n是多少，枚举量都不超过557778）
空间复杂度 $O (1)$

AC代码

C++

class Solution {
private:
    bool isok(int n) {
        int cnt[10] = {0};
        while (n) {
            cnt[n % 10]++;
            n /= 10;
        }
        for (int i = 0; i <= 9; i++) {
            if (cnt[i] && cnt[i] != i) {
                return false;
            }
        }
        return true;
    }

public:
    int nextBeautifulNumber(int n) {
        while (!isok(++n));
        return n;
    }
};

Python

class Solution:
    def ok(self, n: int) -> bool:
        cnt = [0] * 10
        while n:
            cnt[n % 10] += 1
            n //= 10
        for i in range(10):
            if cnt[i] and cnt[i] != i:
                return False
        return True
    
    def nextBeautifulNumber(self, n: int) -> int:
        while True:
            n += 1
            if self.ok(n):
                return n

方法二：打表

方法一中我们实现了“判断一个数是否为数值平衡数的函数”，因此我们可以写一个简单的程序，预先将所有可能用到的“数值平衡数”存下来：

#include <bits/stdc++.h>
using namespace std;
#define mem(a) memset(a, 0, sizeof(a))
#define dbg(x) cout << #x << " = " << x << endl
#define fi(i, l, r) for (int i = l; i < r; i++)
#define cd(a) scanf("%d", &a)
typedef long long ll;

bool isok(int n) {
    int cnt[10] = {0};
    while (n) {
        cnt[n % 10]++;
        n /= 10;
    }
    for (int i = 0; i <= 9; i++) {
        if (cnt[i] && cnt[i] != i) {
            return false;
        }
    }
    return true;
}

int main() {
    vector<int> ok;
    int n = 0;
    while (++n) {
        if (isok(n)) {
            ok.push_back(n);
            if (n > 1000000) {
                break;
            }
        }
    }
    for (int t : ok) {
        cout << t << ", ";
    }
    puts("");
    return 0;
}

上述代码不重要，反正只要能得到下面的这个表就好：

1, 22, 122, 212, 221, 333, 1333, 3133, 3313, 3331, 4444, 14444, 22333, 23233, 23323, 23332, 32233, 32323, 32332, 33223, 33232, 33322, 41444, 44144, 44414, 44441, 55555, 122333, 123233, 123323, 123332, 132233, 132323, 132332, 133223, 133232, 133322, 155555, 212333, 213233, 213323, 213332, 221333, 223133, 223313, 223331, 224444, 231233, 231323, 231332, 232133, 232313, 232331, 233123, 233132, 233213, 233231, 233312, 233321, 242444, 244244, 244424, 244442, 312233, 312323, 312332, 313223, 313232, 313322, 321233, 321323, 321332, 322133, 322313, 322331, 323123, 323132, 323213, 323231, 323312, 323321, 331223, 331232, 331322, 332123, 332132, 332213, 332231, 332312, 332321, 333122, 333212, 333221, 422444, 424244, 424424, 424442, 442244, 442424, 442442, 444224, 444242, 444422, 515555, 551555, 555155, 555515, 555551, 666666, 1224444

这是从1到1224444的所有“数值平衡数”。有了这张表，不论给你的n等于几，你都可以通过二分等方式在极短的时间内找到第一个大于n的“数值平衡数”。

时间复杂度 $\log len(Biao)$ ，其中表的大小 $l e n (B ia o) = 110$
空间复杂度 $O (l e n (B ia o))$

AC代码

C++

const int ok[] = {1, 22, 122, 212, 221, 333, 1333, 3133, 3313, 3331, 4444, 14444, 22333, 23233, 23323, 23332, 32233, 32323, 32332, 33223, 33232, 33322, 41444, 44144, 44414, 44441, 55555, 122333, 123233, 123323, 123332, 132233, 132323, 132332, 133223, 133232, 133322, 155555, 212333, 213233, 213323, 213332, 221333, 223133, 223313, 223331, 224444, 231233, 231323, 231332, 232133, 232313, 232331, 233123, 233132, 233213, 233231, 233312, 233321, 242444, 244244, 244424, 244442, 312233, 312323, 312332, 313223, 313232, 313322, 321233, 321323, 321332, 322133, 322313, 322331, 323123, 323132, 323213, 323231, 323312, 323321, 331223, 331232, 331322, 332123, 332132, 332213, 332231, 332312, 332321, 333122, 333212, 333221, 422444, 424244, 424424, 424442, 442244, 442424, 442442, 444224, 444242, 444422, 515555, 551555, 555155, 555515, 555551, 666666, 1224444};

class Solution {
public:
    int nextBeautifulNumber(int n) {
        return *upper_bound(ok, ok + sizeof(ok) / sizeof(int), n);
    }
};

Python

# from bisect import bisect_right

ok = [1, 22, 122, 212, 221, 333, 1333, 3133, 3313, 3331, 4444, 14444, 22333, 23233, 23323, 23332, 32233, 32323, 32332, 33223, 33232, 33322, 41444, 44144, 44414, 44441, 55555, 122333, 123233, 123323, 123332, 132233, 132323, 132332, 133223, 133232, 133322, 155555, 212333, 213233, 213323, 213332, 221333, 223133, 223313, 223331, 224444, 231233, 231323, 231332, 232133, 232313, 232331, 233123, 233132, 233213, 233231, 233312, 233321, 242444, 244244, 244424, 244442, 312233, 312323, 312332, 313223, 313232, 313322, 321233, 321323, 321332, 322133, 322313, 322331, 323123, 323132, 323213, 323231, 323312, 323321, 331223, 331232, 331322, 332123, 332132, 332213, 332231, 332312, 332321, 333122, 333212, 333221, 422444, 424244, 424424, 424442, 442244, 442424, 442442, 444224, 444242, 444422, 515555, 551555, 555155, 555515, 555551, 666666, 1224444]

class Solution:
    def nextBeautifulNumber(self, n: int) -> int:
        return ok[bisect_right(ok, n)]