当前位置：首页 > news >正文

minimum number

news 2026/5/12 15:01:51

part 1

给一串0到9的数字，返回最小可以组成的整数，以string返回

比如 [1, 3, 3, 4, 2] -> "12334"

所有数字用一遍，0除外，比如[0, 1, 2]就返回12

part 2

part1的基础上返回值要大于或等于一个lower bound

 1 from collections import Counter
 2 
 3 def find_min_greater_or_equal(nums, lower_bound):
 4     s_bound = str(lower_bound)
 5     n = len(s_bound)
 6     nums.sort()  # 排序方便我们取最小值
 7     
 8     def solve(index, is_greater, used_mask):
 9         # 递归终止：已经填完了所有位数
10         if index == n:
11             return ""
12         
13         target = int(s_bound[index])
14         
15         for i in range(len(nums)):
16             if not used_mask[i]:
17                 digit = nums[i]
18                 
19                 # 情况1：之前位已经比 lower_bound 大了，后面全选最小的
20                 if is_greater:
21                     res = solve(index + 1, True, used_mask[:i] + [True] + used_mask[i+1:])
22                     if res is not None:
23                         return str(digit) + res
24                 
25                 # 情况2：当前位和 lower_bound 相同
26                 elif digit == target:
27                     res = solve(index + 1, False, used_mask[:i] + [True] + used_mask[i+1:])
28                     if res is not None:
29                         return str(digit) + res
30                 
31                 # 情况3：当前位第一次比 lower_bound 大
32                 elif digit > target:
33                     res = solve(index + 1, True, used_mask[:i] + [True] + used_mask[i+1:])
34                     if res is not None:
35                         return str(digit) + res
36         
37         return None
38 
39     # 调用递归
40     result = solve(0, False, [False] * len(nums))
41     return int(result) if result else None
42 
43 # 测试例子
44 print(find_min_greater_or_equal([7, 1, 8], 719))  # 输出: 781
45 print(find_min_greater_or_equal([1, 2, 3], 123))  # 输出: 123
46 print(find_min_greater_or_equal([0, 5, 5], 540))  # 输出: 550

比如 [7, 1, 8], lower bound = 719，返回781

Instead of sorting the entire array, we count the occurrences of each digit. Since we only care about 1–9, we iterate through those keys in order to build our string.

 1 def smallest_int_optimized(digits):
 2     # Step 1: Count frequencies - O(N)
 3     counts = [0] * 10
 4     for d in digits:
 5         counts[d] += 1
 6     
 7     # Step 2: Build string from 1 to 9 - O(1) (fixed number of digits)
 8     res = []
 9     for d in range(1, 10):
10         res.append(str(d) * counts[d])
11         
12     return "".join(res)