Tag

【模拟】【取模运算】

---

题目来源

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

---

解题思路

方法一：模拟

思路

观察到数据量 $0<=n<=10^6$，我们可能返回的数值平衡数最大是 1224444，这个范围可以在时间要求内找到答案。

于是从 n+1 开始枚举 x 直到 1224444，统计整数 x 所有数位出现的次数，判断 x 是否是数值平衡数即可。

算法

class Solution {
public:
    int nextBeautifulNumber(int n) {
        function<bool(int)> isBalance = [&](int x) -> bool {
            vector<int> cnts(10);
            while (x) {
                cnts[x %10] ++;
                x /= 10;
            }
            for (int d = 0; d < 10; ++d) {
                if (cnts[d] > 0 && cnts[d] != d) {
                    return false;
                }
            }
            return true;
        };

        for (int i = n + 1; i <= 1224444; ++i) {
            if (isBalance(i)) {
                return i;
            }
        }
        return -1;
    }
};

复杂度分析

时间复杂度：$O(C-n)$，其中 C=1224444 是可能为答案的最大的数值平衡数，取决于题目的数据范围。

空间复杂度：$O(1)$。