下一个更大的数值平衡数

难度: Medium

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

Submission

运行时间: 36 ms

内存: 16.0 MB

class Solution:
    def nextBeautifulNumber(self, n: int) -> int:
        n_str = str(n)
        root_balanced_nums = []
        balanced_nums = []

        def find_root_balanced_nums(root_balanced_num, numLen):
            if len(root_balanced_num) == numLen:
                root_balanced_nums.append(root_balanced_num)
                return

            if numLen - len(root_balanced_num) < int(root_balanced_num[-1]) + 1:
                return

            for nxt_num in range(int(root_balanced_num[-1]) + 1, 10):
                find_root_balanced_nums(root_balanced_num + [str(nxt_num)] * nxt_num, numLen)

        def permute(permutation, root_balanced_num):
            if len(permutation) == len(root_balanced_num):
                balanced_nums.append(''.join(permutation))
                return

            lastpick = None
            for i in range(len(root_balanced_num)):
                if root_balanced_num[i] and root_balanced_num[i] != lastpick:
                    backup = root_balanced_num[i]
                    root_balanced_num[i] = None

                    permute(permutation + [backup], root_balanced_num)

                    root_balanced_num[i] = backup
                    lastpick = root_balanced_num[i]

        for num in range(1, len(n_str) + 1):
            find_root_balanced_nums([str(num)] * num, len(n_str))

        for num in range(1, len(n_str) + 2):
            find_root_balanced_nums([str(num)] * num, len(n_str) + 1)

        for root in root_balanced_nums:
            permute([], root)

        balanced_nums = list(map(lambda x: int(x), balanced_nums))
        balanced_nums.sort()
        
        for num in balanced_nums:
            if int(num) > n:
                return int(num)

Explain

本题解的思路是通过生成所有可能的数值平衡数，然后找到第一个大于给定数n的数值平衡数。首先定义数值平衡数为数位d恰好在数字中出现d次。解题步骤如下： 1. 通过递归尝试构建所有可能的'根平衡数'。'根平衡数'是一个列表，其中的每个元素满足平衡数的条件（即元素值等于其出现次数）。 2. 从长度为len(n)的数开始，尝试构建，然后是len(n)+1。 3. 对于每个生成的'根平衡数'，使用回溯法生成所有可能的排列组合，并将其转换为整数形式存储。 4. 将生成的数值平衡数排序，并找出第一个大于n的数值平衡数。

时间复杂度: O(n!)

空间复杂度: O(n!)

class Solution:
    def nextBeautifulNumber(self, n: int) -> int:
        n_str = str(n)
        root_balanced_nums = []  # 存储'根平衡数'
        balanced_nums = []  # 存储所有可能的数值平衡数

        def find_root_balanced_nums(root_balanced_num, numLen):
            if len(root_balanced_num) == numLen:
                root_balanced_nums.append(root_balanced_num)
                return

            if numLen - len(root_balanced_num) < int(root_balanced_num[-1]) + 1:
                return

            for nxt_num in range(int(root_balanced_num[-1]) + 1, 10):
                find_root_balanced_nums(root_balanced_num + [str(nxt_num)] * nxt_num, numLen)

        def permute(permutation, root_balanced_num):
            if len(permutation) == len(root_balanced_num):
                balanced_nums.append(''.join(permutation))
                return

            lastpick = None
            for i in range(len(root_balanced_num)):
                if root_balanced_num[i] and root_balanced_num[i] != lastpick:
                    backup = root_balanced_num[i]
                    root_balanced_num[i] = None

                    permute(permutation + [backup], root_balanced_num)

                    root_balanced_num[i] = backup
                    lastpick = root_balanced_num[i]

        for num in range(1, len(n_str) + 1):
            find_root_balanced_nums([str(num)] * num, len(n_str))

        for num in range(1, len(n_str) + 2):
            find_root_balanced_nums([str(num)] * num, len(n_str) + 1)

        for root in root_balanced_nums:
            permute([], root)

        balanced_nums = list(map(lambda x: int(x), balanced_nums))
        balanced_nums.sort()
        
        for num in balanced_nums:
            if int(num) > n:
                return int(num)

Explore

这种递归方法确实可能会产生一些重复的计算，特别是在生成所有可能的根平衡数时。时间复杂度主要取决于生成根平衡数和它们的排列的数量。由于根平衡数的生成是基于数字长度的增加，这可能导致指数级增长的根平衡数候选，尤其是在数字长度较长时。此外，对于每个根平衡数，算法还需要生成所有可能的排列组合，进一步增加时间复杂度。总体上，这可能导致非常高的时间复杂度，尤其是对于大数字。空间复杂度也相对较高，因为需要存储所有生成的根平衡数及其排列，这在数字长度较长时尤其显著。

在处理数值平衡数时，数字0的处理方式需要特别注意，因为数值平衡数定义中数字的每个数位d应恰好出现d次，这意味着0如果出现，它的出现次数应该是0次，这是不可能的，因为这将违反数值平衡数的定义。因此，0不应作为数值平衡数的一部分，除非它不是数字的首位。在实际的数字生成过程中，应避免将0作为任何可能生成的数值平衡数的首位数字，同时确保如果0在数字中出现，它的位置不违反数值平衡数的定义。

为确保找到的数值平衡数严格大于给定的n，算法中包含了几个关键的校验步骤。首先，算法从长度等于n的长度开始生成可能的根平衡数，然后扩展到更长的长度，这有助于确保生成的数字不会小于n。其次，所有生成的数值平衡数都转换为整数并排序，然后算法遍历排序后的列表，寻找第一个大于n的数值平衡数。这个过程确保了即使较小的数值平衡数被生成，最终选择的数值平衡数仍然是大于n的最小数。因此，通过这些步骤，可以确保找到的数值平衡数满足题目要求。