Problem

2048. Next Greater Numerically Balanced Number

Analysis

这是上周周赛的一道题,早该写了。

根据题意,11 要么不出现,要么只能出现 11 次,22 同理只能出现 0022 次,则 ii 的出现次数记为 xix_i 的话,就有 xi{0,i}x_i \in \{0, i\}

我们不妨记一个 balanced number 的数位有 mm 个,显然这 mm 个数字只能从集合 {1,2,...,m}\{1,2,...,m\} 里面取,因为如果你取了 m+1m+1,则根据规则它必须出现 m+1m+1 次,我们只有 mm 个数位,显然放不开,至于 0。它只能出现 0 次,直接没法用。

既然知道了每个数位的取值集合,那我们就可以考察集合内每个元素在 mm 个数位中的出现次数,不妨记数字 ii 出现了 xix_i 次,其中 i{1,2,...,m},xi{0,i}i \in \{1,2,...,m\}, x_i \in \{0, i\}。则有 i=1mxi=m,xi{0,i}\sum_{i=1}^{m}x_i = m, x_i \in \{0, i\}

举个具体的例子,假设 m=4m=4,那就是 x1+x2+x3+x4=4x_1 + x_2 + x_3 + x_4 = 4 并且每个变量要么取 0 要么取下标值,即有如下两种取值方式:

x1=x2=x3=0,x4=4x1=1,x3=3,x2=x4=0\begin{align*} x_1 &= x_2 = x_3 = 0, x_4 = 4 \\ x_1 &= 1, x_3 = 3, x_2 = x_4 = 0 \end{align*}

也就是说对于 4 位数,只有 4444444413331333 全及其排列是 balanced number。

如果 mm 很大,比如一万位,那么我们需要依照公式使用回溯法逐渐试探出所有可能的取值方式。但是这个题目限定了取值范围,最大就是 6 位数,所以我们可以直接打表,先把所有可能的取值算出来,如下:

1
2
table = [1, 22, 221, 333, 1333, 4444, 14444,
22333, 55555, 122333, 155555, 224444, 666666, 1224444]

然后遍历每个元素,求每个元素的 nextPermutation,看这些 Permutation 中哪个比输入的目标数字 nn 大,且是满足要求的最小数字。注意这个思路看起来可以继续优化,比如我上面的数组是增序的,对每个元素生成 nextPermutation 应该也是增序才对,但是并不是,比如 41444>2222241444 > 22222,所以优化起来很麻烦,每个元素的全排列在数字大小范围上有重叠。就这样时间复杂度已经足够了。

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution:
def reverse(self, nums, a, b):
i = a
j = b
while i < j:
nums[i], nums[j] = nums[j], nums[i]
i += 1
j -= 1
def nextPermutation(self, nums: List[int]) -> None:
"""Do not return anything, modify nums in-place instead."""
n = len(nums)
i = n-1
while i >= 1:
if nums[i] <= nums[i-1]:
i -= 1
else:
break
if i == 0:
self.reverse(nums, 0, n-1)
return
j = n-1
_min = nums[n-1]
while j >= i:
if nums[j] <= nums[i-1]:
j -= 1
continue
else:
break
nums[i-1], nums[j] = nums[j], nums[i-1]
self.reverse(nums, i, n-1)

def nextBeautifulNumber(self, n: int) -> int:
if n == 0:
return 1
table = [1, 22, 221, 333, 1333, 4444, 14444,
22333, 55555, 122333, 155555, 224444, 666666, 1224444]
res = 10000000
for x in table:
tmp = x
nums = []
while tmp:
nums.insert(0, tmp%10)
tmp = tmp//10
while True:
self.nextPermutation(nums)
num = 0
for j in range(len(nums)):
num = num * 10 + nums[j]
if num > n and num < res:
res = num
if num == x:
break
return res