数组组成的最小数字 - 华为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. 数组长度判断：
   • 如果数组长度为1，直接输出该元素。
   • 如果数组长度为2，计算两种不同的组合，取最小值。
   • 如果数组长度大于等于3，进行全排列组合，找到由3个元素组成的最小数字。
2. 排列组合：当数组长度大于等于3时，可以通过遍历所有3个元素的排列，依次生成这些排列所形成的数，并记录最小的数值。
3. 贪心策略：为了使得最终的数最小，我们需要比较不同的排列所形成的数字，选择其中最小的一个。这就是典型的贪心算法思想：每一步都选择局部最优的排列。

代码大致描述

无论是哪种语言实现，整体思路大致相同：

1. 输入解析：将输入的字符串按逗号分割成一个数组。
2. 特殊情况处理：如果数组长度小于3，直接返回组合后的最小值。
3. 全排列查找最小值：遍历数组，选择三个不同的元素，生成所有可能的数字组合，最后返回最小的数字。
4. 输出结果：打印最小的组合数。

时间复杂度

• 时间复杂度：
  • 如果数组长度为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;
        }