数组组成的最小数字 - 华为OD统一考试(E卷)
2024华为OD机试（E卷+D卷+C卷）最新题库【超值优惠】Java/Python/C++合集
题目描述
给定一个整型数组，请从该数组中选择3个元素组成最小数字并输出(如果数组长度小于3，则选择数组中所有元素来组成最小数字)。
输入描述
一行用半角逗号分割的字符串记录的整型数组，0<数组长度<=100，0<整数的取值范围<=10000。
输出描述
由3个元素组成的最小数字，如果数组长度小于3，则选择数组中所有元素来组成最小数字。
示例1
输入：
21,30,62,5,31
输出：
21305
说明：
数组长度超过3，需要选3个元素组成最小数字，21305由21,30,5三个元素组成的数字，为所有组合中最小的数字
示例2
输入：
5,21
输出：
215
说明：
数组长度小于3，选择所有元素来主城最小值，215为最小值。
题解
题目类型
该题属于贪心算法的应用，因为我们需要在给定的条件下，组合数字，使得最终结果最小。通过排列组合元素并比较组合后的结果大小，我们可以找到符合要求的最小数。
解题思路
题目要求从数组中选择3个元素，组成最小的数字，并且如果数组长度小于3，则直接将所有元素组成最小的数字。解题的核心在于如何组合这3个数字使得结果最小。可以通过全排列来生成所有可能的组合，然后找到最小的一个。具体解题步骤如下：
- 数组长度判断：
- 如果数组长度为1，直接输出该元素。
- 如果数组长度为2，计算两种不同的组合，取最小值。
- 如果数组长度大于等于3，进行全排列组合，找到由3个元素组成的最小数字。
- 排列组合：当数组长度大于等于3时，可以通过遍历所有3个元素的排列，依次生成这些排列所形成的数，并记录最小的数值。
- 贪心策略：为了使得最终的数最小，我们需要比较不同的排列所形成的数字，选择其中最小的一个。这就是典型的贪心算法思想：每一步都选择局部最优的排列。
代码大致描述
无论是哪种语言实现，整体思路大致相同：
- 输入解析：将输入的字符串按逗号分割成一个数组。
- 特殊情况处理：如果数组长度小于3，直接返回组合后的最小值。
- 全排列查找最小值：遍历数组，选择三个不同的元素，生成所有可能的数字组合，最后返回最小的数字。
- 输出结果：打印最小的组合数。
时间复杂度
- 时间复杂度：
- 如果数组长度为n，当n≥3时，生成三个元素的所有组合所需时间复杂度为O(n^3)。
- 数组中每次组合后的字符串拼接操作为常数时间，比较字符串形成的整数也为常数时间。
- 空间复杂度：由于只使用了几个变量来存储最小值和临时组合，空间复杂度为O(1)，输入数组的存储空间不计算在内。
Java
import java.util.Scanner;
/**
* @author code5bug
*/
public class Main {
public static void main(String[] args) throws Exception {
Scanner in = new Scanner(System.in);
String[] arr = in.nextLine().split(",");
int n = arr.length; // 获取输入的长度
// 只有一个元素时，直接输出
if (n == 1) {
System.out.println(arr[0]);
return;
}
// 如果有两个元素，则比较两种组合，输出最小值
if (n == 2) {
String s1 = arr[0], s2 = arr[1];
System.out.println(Math.min(Long.parseLong(s1 + s2), Long.parseLong(s2 + s1)));
return;
}
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
华为OD机试题库题解2024 文章被收录于专栏
华为OD机考（CDE卷）题库（绝对都是原题），帮助你上岸华为（已经不少小伙伴成功上岸）。提供Java、Python、C++ 三种语言的解法。每篇文章都有详细的解题步骤、代码注释详细及相关知识点的练习题。有问题，随时解答。
查看49道真题和解析
