

























part 1
给一串0到9的数字,返回最小可以组成的整数,以string返回
比如 [1, 3, 3, 4, 2] -> "12334"
所有数字用一遍,0除外,比如[0, 1, 2]就返回12
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)
part 2
part1的基础上返回值要大于或等于一个lower bound
比如 [7, 1, 8], lower bound = 719,返回781
1 from collections import Counter 2 3 def find_min_greater_equal_counter(nums, lower_bound): 4 s_bound = str(lower_bound) 5 n = len(s_bound) 6 # 统计每个数字出现的频率 7 counts = Counter(nums) 8 # 获取去重后的有序数字列表 9 unique_digits = sorted(counts.keys()) 10 11 def solve(index, is_greater): 12 if index == n: 13 return "" 14 15 target = int(s_bound[index]) 16 17 for d in unique_digits: 18 if counts[d] > 0: 19 # 剪枝:如果还没超越 bound 且当前数字太小,跳过 20 if not is_greater and d < target: 21 continue 22 23 # 尝试放置数字 d 24 counts[d] -= 1 25 res = solve(index + 1, is_greater or (d > target)) 26 27 if res is not None: 28 return str(d) + res 29 30 # 回溯 31 counts[d] += 1 32 33 return None 34 35 return solve(0, False)
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。