Medium

题目描述

一个整数 x 是数值平衡的，当且仅当对于数字 x 中的每个数字 d，数字 d 在 x 中恰好出现 d 次。

给定一个整数 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 能有多远？
  • 在给定约束下，最大的数值平衡数是什么？

解题思路

解题思路

这道题要求找到严格大于给定数字 n 的最小数值平衡数。数值平衡数的定义是：对于数字中的每个数字 d，它在整个数字中恰好出现 d 次。

方法一：枚举法（推荐）

由于约束条件 n ≤ 10^6，我们可以直接从 n+1 开始枚举每个数字，检查它是否为数值平衡数。这种方法简单直接，且由于数值平衡数相对稀少，不会超时。

检查数值平衡数的步骤：

  1. 统计数字中每个数位的出现次数
  2. 检查每个出现的数位 d 是否恰好出现 d 次
  3. 特别注意数字 0：如果 0 出现，那么它必须出现 0 次（矛盾），所以包含 0 的数字不可能是数值平衡数

方法二：预计算

我们可以预先生成所有可能的数值平衡数，然后使用二分查找。但考虑到约束范围不大，方法一已经足够高效。

通过分析可知，在给定范围内，最大的数值平衡数是 1333333（7位数），所以枚举的范围是有限的。

代码实现

class Solution {
public:
    int nextBeautifulNumber(int n) {
        for (int num = n + 1; ; num++) {
            if (isBeautiful(num)) {
                return num;
            }
        }
    }
    
private:
    bool isBeautiful(int num) {
        vector<int> count(10, 0);
        int temp = num;
        
        // 统计每个数位的出现次数
        while (temp > 0) {
            count[temp % 10]++;
            temp /= 10;
        }
        
        // 检查是否为数值平衡数
        for (int i = 0; i < 10; i++) {
            if (count[i] != 0 && count[i] != i) {
                return false;
            }
        }
        return true;
    }
};

class Solution:
    def nextBeautifulNumber(self, n: int) -> int:
        def is_beautiful(num):
            count = [0] * 10
            temp = num
            
            # 统计每个数位的出现次数
            while temp > 0:
                count[temp % 10] += 1
                temp //= 10
            
            # 检查是否为数值平衡数
            for i in range(10):
                if count[i] != 0 and count[i] != i:
                    return False
            return True
        
        num = n + 1
        while True:
            if is_beautiful(num):
                return num
            num += 1

public class Solution {
    public int NextBeautifulNumber(int n) {
        for (int num = n + 1; ; num++) {
            if (IsBeautiful(num)) {
                return num;
            }
        }
    }
    
    private bool IsBeautiful(int num) {
        int[] count = new int[10];
        int temp = num;
        
        // 统计每个数位的出现次数
        while (temp > 0) {
            count[temp % 10]++;
            temp /= 10;
        }
        
        // 检查是否为数值平衡数
        for (int i = 0; i < 10; i++) {
            if (count[i] != 0 && count[i] != i) {
                return false;
            }
        }
        return true;
    }
}

var nextBeautifulNumber = function(n) {
    function isBeautiful(num) {
        const count = new Array(10).fill(0);
        let temp = num;
        
        // 统计每个数位的出现次数
        while (temp > 0) {
            count[temp % 10]++;
            temp = Math.floor(temp / 10);
        }
        
        // 检查是否为数值平衡数
        for (let i = 0; i < 10; i++) {
            if (count[i] !== 0 && count[i] !== i) {
                return false;
            }
        }
        return true;
    }
    
    for (let num = n + 1; ; num++) {
        if (isBeautiful(num)) {
            return num;
        }
    }
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(k × log k)，其中 k 是下一个数值平衡数与 n 的差值，log k 是检查每个数字的位数
空间复杂度O(1)，只使用固定大小的数组存储数位计数

相关题目