华为OD机试_2025 B卷_数组组成的最小数字（Python，100分）（附详细解题思路）
题目描述
给定一个整型数组，请从该数组中选择3个元素组成最小数字并输出
（如果数组长度小于3，则选择数组中所有元素来组成最小数字）。
输入描述
一行用半角逗号分割的字符串记录的整型数组，0 < 数组长度 <= 100，0 < 整数的取值范围 <= 10000。
输出描述
由3个元素组成的最小数字，如果数组长度小于3，则选择数组中所有元素来组成最小数字。
用例
| 输入 | 21,30,62,5,31 |
| 输出 | 21305 |
| 说明 | 数组长度超过3，需要选3个元素组成最小数字，21305由21,30,5三个元素组成的数字，为所有组合中最小的数字。 |
| 输入 | 5,21 |
| 输出 | 215 |
| 说明 | 数组长度小于3， 选择所有元素来组成最小值，215为最小值。 |
核心解题思路
题目要求从数组中选择3个元素（或更少）组成一个尽可能小的数字。例如，输入21,30,62,5,31时，组合21,30,5可以拼接成21305，这是所有可能组合中最小的。关键在于如何高效枚举所有可能的组合，并找到每个组合的最小排列方式。
解题步骤详解
1. 输入处理与参数设置
- 将输入字符串按逗号分割为字符串列表，保留原数字的前导零（如
05）。 - 确定需要选择的元素数量
k：k = min(3, len(nums)) if nums else 0 # nums是输入的数组
2. 枚举所有可能的组合
生成所有长度为k的组合。例如，数组长度n=5时，生成C(5,3)=10种组合。
3. 对每个组合生成全排列并找最小值
对于每个组合生成所有排列（例如k=3时有6种排列），将每个排列拼接成字符串，取最小字符串：
current_min = min(''.join(p) for p in permutations(combo))
4. 全局最小值维护
在所有组合的最小拼接结果中，保存全局最小的字符串。
完整代码实现
import itertoolsnums = input().strip().split(',')
k = min(3, len(nums))
min_result = None# 遍历所有k元素的组合
for combo in itertools.combinations(nums, k):# 生成该组合的全排列，并计算最小拼接结果current_min = min(''.join(p) for p in itertools.permutations(combo))# 更新全局最小值if min_result is None or current_min < min_result:min_result = current_minprint(min_result)
关键逻辑解析
1. 组合生成
通过itertools.combinations生成所有可能的组合：
itertools.combinations(nums, k)
- 例如，
nums=['21','30','5']时，生成唯一的组合('21','30','5')。
2. 排列生成与拼接
对每个组合生成全排列，并转换为字符串：
itertools.permutations(combo) # 生成排列
''.join(p) # 拼接字符串
- 示例组合的排列包括
('21','30','5')、('21','5','30')等，转换为'21305'、'21530'等。
3. 最小值比较
通过字符串字典序直接比较大小。例如：
'21305' < '21530' # True，因此保留前者
复杂度分析
- 组合数量：当
k=3且n=100时，组合数为C(100,3)=161700。 - 排列数量：每个组合生成
3!=6种排列。 - 总操作次数：
161700 * 6 = 970200次拼接和比较，在Python中可轻松处理。
示例验证
示例1：
输入：
21,30,62,5,31
处理流程：
- 生成10种组合。
- 组合
['21','30','5']的最小拼接为21305。 - 其他组合的最小值均不小于
21305。
输出：21305
示例2：
输入：
5,21
处理流程：
- 组合为
['5','21']。 - 排列拼接结果为
521和215，取215。
输出：215
总结
通过枚举所有可能的元素组合，并对每个组合生成全排列后取最小值，可以确保找到全局最优解。虽然时间复杂度较高，但在题目限制下完全可行。核心技巧在于利用字符串字典序比较，直接生成最小可能的拼接结果。