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)$。