Skip to content

Latest commit

 

History

History
202 lines (165 loc) · 4.64 KB

File metadata and controls

202 lines (165 loc) · 4.64 KB
comments difficulty edit_url rating source tags
true
中等
1734
第 264 场周赛 Q2
数学
回溯
枚举

English Version

题目描述

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

解法

方法一:枚举

我们注意到,题目中 $n$ 的范围是 $[0, 10^6]$,而大于 $10^6$ 的其中一个数值平衡数是 $1224444$,因此我们直接枚举 $x \in [n + 1, ..]$,然后判断 $x$ 是否是数值平衡数即可。枚举的 $x$ 一定不会超过 $1224444$

时间复杂度 $O(M - n)$,其中 $M = 1224444$。空间复杂度 $O(1)$

Python3

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

Java

class Solution {
    public int nextBeautifulNumber(int n) {
        for (int x = n + 1;; ++x) {
            int[] cnt = new int[10];
            for (int y = x; y > 0; y /= 10) {
                ++cnt[y % 10];
            }
            boolean ok = true;
            for (int y = x; y > 0; y /= 10) {
                if (y % 10 != cnt[y % 10]) {
                    ok = false;
                    break;
                }
            }
            if (ok) {
                return x;
            }
        }
    }
}

C++

class Solution {
public:
    int nextBeautifulNumber(int n) {
        for (int x = n + 1;; ++x) {
            int cnt[10]{};
            for (int y = x; y > 0; y /= 10) {
                ++cnt[y % 10];
            }
            bool ok = true;
            for (int y = x; y > 0; y /= 10) {
                if (y % 10 != cnt[y % 10]) {
                    ok = false;
                    break;
                }
            }
            if (ok) {
                return x;
            }
        }
    }
};

Go

func nextBeautifulNumber(n int) int {
	for x := n + 1; ; x++ {
		cnt := [10]int{}
		for y := x; y > 0; y /= 10 {
			cnt[y%10]++
		}
		ok := true
		for y := x; y > 0; y /= 10 {
			if y%10 != cnt[y%10] {
				ok = false
				break
			}
		}
		if ok {
			return x
		}
	}
}

TypeScript

function nextBeautifulNumber(n: number): number {
    for (let x = n + 1; ; ++x) {
        const cnt: number[] = Array(10).fill(0);
        for (let y = x; y > 0; y = (y / 10) | 0) {
            cnt[y % 10]++;
        }
        let ok = true;
        for (let i = 0; i < 10; ++i) {
            if (cnt[i] && cnt[i] !== i) {
                ok = false;
                break;
            }
        }
        if (ok) {
            return x;
        }
    }
}