Tag
【模拟】【取模运算】
题目来源
2048. 下一个更大的数值平衡数

解题思路
方法一:模拟
思路
观察到数据量 0 < = n < = 1 0 6 0<= n <=10^6 0<=n<=106,我们可能返回的数值平衡数最大是 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 ) O(C−n) O(C−n),其中 C=1224444
是可能为答案的最大的数值平衡数,取决于题目的数据范围。
空间复杂度: O ( 1 ) O(1) O(1)。