数组组成的最小数字 - 华为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;}// 三个元素的全排列组合，找到最小值long result = Long.MAX_VALUE;for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (i == j) continue;for (int k = 0; k < n; k++) {if (i == k || j == k) continue;// 将三个数字组合成一个字符串，再转化为 long 值进行比较String s = arr[i] + arr[j] + arr[k];result = Math.min(result, Long.parseLong(s));}}}// 输出最终的最小值结果System.out.println(result);}
}

Python

def solve():# 从标准输入读取数据arr = input().split(",")n = len(arr)# 只有一个元素时，直接输出if n == 1:print(arr[0])# 如果有两个元素，则比较两种组合，输出最小值elif n == 2:s1, s2 = arr[0], arr[1]print(min(int(s1 + s2), int(s2 + s1)))else:# 三个元素的全排列组合，找到最小值result = float('inf')  # 设置初始值为无穷大for i in range(n):for j in range(n):if i == j:continuefor k in range(n):if i == k or j == k:continue# 将三个数字组合成一个字符串，再转化为整数进行比较s = arr[i] + arr[j] + arr[k]result = min(result, int(s))# 输出最终的最小值结果print(result)if __name__ == "__main__":solve()

C++

#include <iostream>
#include <string>
#include <vector>using namespace std;int main() {vector<int> arr;int num;while (cin >> num) {arr.push_back(num);if (cin.peek() == '\n') break;cin.ignore();}int n = arr.size();// 只有一个元素时if (n == 1) {cout << arr[0] << endl;return 0;}// 两个元素组成数字if (n == 2) {string s1 = to_string(arr[0]), s2 = to_string(arr[1]);cout << min(stoll(s1 + s2), stoll(s2 + s1)) << endl;return 0;}long long result = LONG_LONG_MAX;for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (i == j) continue;for (int k = 0; k < n; k++) {if (i == k || j == k) continue;// 三个元素组成数字string s = to_string(arr[i]) + to_string(arr[j]) + to_string(arr[k]);result = min(result, stoll(s));}}}cout << result << endl;return 0;
}