LeetCode 题解工作台
下一个更大的数值平衡数
如果整数 x 满足：对于每个数位 d ，这个数位 恰好 在 x 中出现 d 次。那么整数 x 就是一个 数值平衡数 。 给你一个整数 n ，请你返回 严格大于 n 的 最小数值平衡数 。 示例 1： 输入： n = 1 输出： 22 解释： 22 是一个数值平衡数，因为： - 数字 2 出现 2 次…
5
题型
6
代码语言
3
相关题
当前训练重点
中等 · 回溯·pruning
答案摘要
我们注意到，题目中 的范围是 $[0, 10^6]$，而大于 的其中一个数值平衡数是 ，因此我们直接枚举 $x \in [n + 1, ..]$，然后判断 是否是数值平衡数即可。枚举的 一定不会超过 。 时间复杂度 $O(M - n)$，其中 $M = 1224444$。空间复杂度 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 回溯·pruning 题型思路
题目描述
如果整数 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 <= 106
解题思路
方法一：枚举
我们注意到，题目中 的范围是 ，而大于 的其中一个数值平衡数是 ，因此我们直接枚举 ，然后判断 是否是数值平衡数即可。枚举的 一定不会超过 。
时间复杂度 ，其中 。空间复杂度 。
class Solution:
def nextBeautifulNumber(self, n: int) -> int:
for x in count(n + 1):
y = x
cnt = [0] * 10
while y:
y, v = divmod(y, 10)
cnt[v] += 1
if all(v == 0 or i == v for i, v in enumerate(cnt)):
return x
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Ability to optimize a backtracking solution using pruning.
- question_mark
Understanding of how digit counts relate to number structure.
- question_mark
Proficiency in using hash tables for counting occurrences.
常见陷阱
外企场景- error
Failing to prune the search space effectively, leading to inefficient exploration.
- error
Incorrectly assuming that a number is balanced without verifying digit counts.
- error
Overcomplicating the counting of digits, missing simple checks that could speed up the solution.
进阶变体
外企场景- arrow_right_alt
Implementing the solution without using backtracking.
- arrow_right_alt
Optimizing the counting process by using other data structures besides a hash table.
- arrow_right_alt
Considering a more brute force approach without pruning.