【华为OD-E卷 - 组合出合法最小数 100分（python、java、c++、js、c）】
题目
给一个数组，数组里面哦都是代表非负整数的字符串，将数组里所有的数值排列组合拼接起来组成一个数字，输出拼接成的最小的数字
输入描述
- 一个数组，数组不为空，数组里面都是代表非负整数的字符串，可以是0开头，例如：[“13”, “045”, “09”, “56”]。
数组的大小范围：[1, 50]
数组中每个元素的长度范围：[1, 30]
输出描述
- 以字符串的格式输出一个数字，
如果最终结果是多位数字，要优先选择输出不是“0”开头的最小数字 如果拼接出来的数字都是“0”开头，则选取值最小的，并且把开头部分的“0”都去掉再输出 如果是单位数“0”，可以直接输出“0”
用例
用例一：
输入：
20 1
输出：
120
用例二：
输入：
08 10 2
输出：
10082
用例三：
输入：
01 02
输出：
102
python解法
- 解题思路：
- 这道题目要求的是给定一组数字，组合成一个最小的数字。我们可以把每个数字视为字符串，比较不同数字的拼接顺序，找到使得拼接后的结果最小的顺序。
比较规则：对于任意两个数字 x 和 y，我们将它们拼接成两种顺序的字符串：x + y 和 y + x，然后比较它们的大小。若 x + y 小于 y + x，则 x 应该排在前面；反之，则 y 排在前面。
排序：根据上述的比较规则，将数字按顺序排列。
去除前导零：排序后得到的数字可能会有前导零，特别是当数组中包含多个零时。需要去除这些前导零。
特殊情况：如果排序后的数字全部是零（例如输入的是 [0, 0, 0]），则最终结果应该是 “0”。
from functools import cmp_to_key
def min_combination(arr):
# 自定义比较函数：比较拼接后的两个字符串的大小
def compare(x, y):
# 比较 x + y 和 y + x 两种拼接方式的结果
return -1 if x + y < y + x else 1 if x + y > y + x else 0
# 使用 sorted 排序数组，排序的依据是自定义的比较函数
sorted_arr = sorted(arr, key=cmp_to_key(compare))
# 将排序后的数组拼接成一个字符串，并去除前导零
result = ''.join(sorted_arr).lstrip('0')
# 如果拼接结果为空字符串（说明原始数组全是零），返回 '0'
return result if result else '0'
if __name__ == "__main__":
# 输入数组并进行处理
arr = input().split()
# 输出最小组合数字
print(min_combination(arr))
java解法
- 解题思路
- 本题要求将若干个数字组合成一个最小的数字。在解决过程中，我们需要考虑两方面：
数字排序规则：对于每一对数字，比较它们的拼接顺序。例如，两个数字 a 和 b，我们需要比较 a + b 和 b + a，然后决定它们的顺序。拼接后较小的排列应该排在前面。
特殊处理零的情况：如果所有的数字都是零（例如 0 0 0），那么最终的结果应为单一的 “0”。
解题步骤：
输入分离：首先将输入的数字分为两类：一类是以零开头的数字（例如 0, 00 等），另一类是非零开头的数字。
排序规则：
对于零开头的数字，直接按拼接后顺序排序。
对于非零开头的数字，按字典序排序（最小的在前）。
拼接组合：
对于零开头的数字，直接拼接起来并去掉前导零。
对于非零开头的数字，找到最优的组合顺序。通过对这些数字进行排序，拼接成最小的结果。
去除前导零：最后将拼接后的数字去掉可能的前导零，特别是在数字全为零的情况下，返回 “0”。
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 读取输入的数字并分割成数组
String[] arr = sc.nextLine().split(" ");
MinNumberFinder finder = new MinNumberFinder(arr);
// 输出最小组合数字
System.out.println(finder.getMinNumber());
}
}
class MinNumberFinder {
private List<String> zList; // 存储以零开头的数字
private List<String> nzList; // 存储非零开头的数字
// 构造函数，根据输入数组初始化并分离数字
public MinNumberFinder(String[] arr) {
this.zList = new ArrayList<>();
this.nzList = new ArrayList<>();
splitNumbers(arr);
}
// 分离数字：将零开头的数字放入 zList，其余放入 nzList
private void splitNumbers(String[] arr) {
for (String val : arr) {
if (val.charAt(0) == '0') { // 以零开头的数字
zList.add(val);
} else { // 非零开头的数字
nzList.add(val);
}
}
}
// 获取最小组合数字
public String getMinNumber() {
// 排序两个列表
sortLists();
// 将零开头的数字拼接起来
StringBuilder zStr = combineList(zList);
// 如果没有非零数字，则直接返回零开头部分
if (nzList.isEmpty()) {
return formatResult(zStr);
}
// 否则，找到最优的非零数字组合顺序
return findBestCombination(zStr);
}
// 排序：零开头的数字按拼接顺序排序，非零开头的数字按字典序排序
private void sortLists() {
zList.sort((a, b) -> (a + b).compareTo(b + a)); // 零开头数字排序规则
nzList.sort((a, b) -> a.compareTo(b)); // 非零开头数字字典序排序
}
// 拼接列表中的字符串
private StringBuilder combineList(List<String> list) {
StringBuilder sb = new StringBuilder();
for (String s : list) {
sb.append(s);
}
return sb;
}
// 格式化零开头的字符串：去除前导零
private String formatResult(StringBuilder zStr) {
String result = zStr.toString().replaceFirst("^0+", ""); // 去除前导零
return result.isEmpty() ? "0" : result; // 如果为空，说明全部是零，返回 "0"
}
// 寻找最优的非零数字组合
private String findBestCombination(StringBuilder zStr) {
List<String> hList = new ArrayList<>();
hList.add(nzList.remove(0)); // 取出第一个非零数字
// 如果头部元素与下一个非零元素相同，继续取出元素
while (!nzList.isEmpty() && hList.get(0).charAt(0) == nzList.get(0).charAt(0)) {
hList.add(nzList.remove(0));
}
String bestResult = null;
// 遍历每一种可能的排列顺序，找到字典序最小的组合
for (int i = 0; i < hList.size(); i++) {
String head = hList.get(i);
List<String> tail = new ArrayList<>(nzList); // 剩余的非零数字
tail.addAll(hList.subList(0, i)); // 拼接当前头部前的部分
tail.addAll(hList.subList(i + 1, hList.size())); // 拼接当前头部后的部分
// 对尾部数字按拼接顺序进行排序
tail.sort((a, b) -> (a + b).compareTo(b + a));
// 构建当前的组合结果
String tempResult = head + zStr + combineList(tail);
if (bestResult == null || tempResult.compareTo(bestResult) < 0) {
bestResult = tempResult;
}
}
return bestResult;
}
}
C++解法
- 解题思路
更新中
C解法
更新中
JS解法
更新中
注意：
如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏