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:
continue
for 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;
}
相关练习题
| 题号 | 题目 | 难易 |
|---|---|---|
| LeetCode 179 | 179. 最大数 | 中等 |
| LeetCode 321 | 321. 拼接最大数 | 困难 |
整理题解不易， 如果有帮助到您，请给点个赞 ❤️ 和收藏 ⭐，让更多的人看到。
标签：arr,OD,int,元素,最小,华为,数组,最小值 From： https://blog.csdn.net/user_longling/article/details/142453113