题目

如果整数 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^6

解题思路

这道题的解题思路是：从 n+1 开始，逐个检查每个整数，直到找到第一个“数值平衡数”为止。

这个思路之所以可行，是因为题目给定的 n 的范围（$n≤10^6$）并不大，而且“数值平衡数”在数轴上的分布虽然稀疏，但两个连续的平衡数之间的“空隙”也不会大到无法接受。

分析“数值平衡数”的特性

根据定义：对于每个在 $x$ 中出现的数位 $d$，$d$ 必须恰好出现 $d$ 次。

关键特性：数值平衡数中不能包含数字 0。
- 为什么？如果数字 0 出现了，根据定义，它必须出现 0 次。这本身就是一个矛盾。
- 因此，我们只需要考虑由 {1, 2, 3, 4, 5, 6, 7, 8, 9} 组成的数字。
例子：
- 22：数字 2 出现了 2 次。
- 1333：数字 1 出现了 1 次，数字 3 P 出现了 3 次。
- 122：数字 1 出现了 1 次，数字 2 出现了 2 次。

分析数据范围（$n≤10^6$）

我们需要的答案是严格大于 $n$ 的最小平衡数。我们来看看 $n$ 在最大值 $10^6$ 附近的情况。

$n=1,000,000$。
我们需要找到一个大于 $10^6$（即一个七位数）的最小平衡数。
一个平衡数的“长度”（即位数）等于它所包含的数位之和。例如 1333 的长度是 1+3=4。
我们要找一个长度为 7 的最小平衡数。我们需要找到一组数字 ${d_1, d_2, ...}$，使得它们的和为 7。
- {7} -> 组成的数字是 7777777。
- {1, 6} -> 组成的数字是 {1, 6, 6, 6, 6, 6, 6}。最小的排列是 1666666。
- {2, 5} -> 组成的数字是 {2, 2, 5, 5, 5, 5, 5}。最小的排列是 2255555。
- {3, 4} -> 组成的数字是 {3, 3, 3, 4, 4, 4, 4}。最小的排列是 3334444。
- {1, 2, 4} -> 组成的数字是 {1, 2, 2, 4, 4, 4, 4}。最小的排列是 1224444。
比较上面这些7位数，最小的是 1224444。
这意味着，当 $n=10^6$ 时，我们要找的答案是 1224444。
在最坏的情况下（例如 $n=1,000,001$），我们也只需要从 1,000,002 迭代检查到 1,224,444，这个计算量（约22万次检查）是非常小的，完全可以在限制时间内完成。

算法设计

基于以上的分析，我们可以采用简单的“迭代搜索”策略。

主函数：nextBalancedNumber(n)

从 x = n + 1 开始循环。
在循环中，调用一个辅助函数 isBalanced(x) 来检查当前的 x 是否是数值平衡数。
如果 isBalanced(x) 返回 true，那么 x 就是我们要找的答案，直接返回 x。
如果返回 false，则 x++，继续下一次循环。

辅助函数：isBalanced(num)

这个函数用于判断一个数 num 是否是数值平衡数。

创建一个大小为 10 的数组（或哈希表） counts，用于统计 0-9 每个数字出现的次数。
遍历 num 的每一位（可以通过循环取模 % 10 和整除 / 10 来实现）。
在遍历时，用 counts 数组记录每个数位 d 出现的次数 counts[d]。
遍历完成后，检查 counts 数组（从索引 i=0 到 9）：
- 检查 0： 如果 counts[0] > 0，说明数字 0 出现了，这违反了平衡数的特性，直接返回 false。
- 检查 1-9： 如果 counts[i] > 0 (表示数位 i 至少出现了一次)，并且 counts[i] != i (表示它出现的次数不等于 i)，则不满足平衡数定义，返回 false。
如果 counts 数组的所有检查都通过了，说明 num 是一个数值平衡数，返回 true。

具体代码

func nextBeautifulNumber(n int) int {
	for x := n + 1; ; x++ {
		if isBalanced(x) {
			return x
		}
	}
}

// 数值平衡数判定：出现过的数字 d，其出现次数必须恰好等于 d；且不能含有 0。
func isBalanced(x int) bool {
	cnt := [10]int{}
	y := x
	for y > 0 {
		d := y % 10
		cnt[d]++
		y /= 10
	}
	// 不能含 0（因为 0 出现次数必须是 0）
	if cnt[0] > 0 {
		return false
	}
	// 对于出现过的数字 d（1..9），出现次数必须等于 d
	for d := 1; d <= 9; d++ {
		if cnt[d] > 0 && cnt[d] != d {
			return false
		}
	}
	return true
}

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

beautifulremi

题目

解题思路

具体代码