【华为OD】MVP争夺战2（C++、Java、Python）

文章目录

• 题目
• • 题目描述
  • 输入描述
  • 输出描述
  • 示例
• 思路
• • 核心思路：
  • 关键观察：
  • 算法步骤：
  • 排序策略：
  • 特殊情况处理：
• 代码
• • C++
  • Java
  • Python
• 复杂度分析
• • 时间复杂度
  • 空间复杂度
• 结果
• 总结

题目

题目描述

给定一个整型数组，请从该数组中选择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为最小值。

题目链接🔗

思路

这是一个数字组合优化问题，需要找到能组成最小数字的策略：

核心思路：

1. 数组长度 < 3： 直接使用所有元素
2. 数组长度 ≥ 3： 选择3个元素，使组成的数字最小

关键观察：

• 要让组成的数字最小，需要考虑两个因素：
  1. 数字位数越少越好
  2. 高位数字越小越好

算法步骤：

1. 数字排序： 按数值大小升序排列，选择前3个较小的数字
2. 组合排序： 对选中的数字按照拼接结果的字典序排序
3. 拼接输出： 将排序后的数字拼接成最终结果

排序策略：

关键在于第二步的排序规则：对于两个数字 a 和 b，如果 a+b < b+a（字符串拼接比较），则 a 应该排在 b 前面。

例如：

• 数字 21 和 30：比较 “2130” 和 “3021”，因为 “2130” < “3021”，所以 21 排在 30 前面
• 数字 30 和 5：比较 “305” 和 “530”，因为 “305” < “530”，所以 30 排在 5 前面

特殊情况处理：

• 数组长度 < 3 时，直接对所有元素按组合规则排序
• 数组长度 ≥ 3 时，先选择数值最小的3个元素，再按组合规则排序

代码

C++

#include #include #include #define MIN(a,b) ((a) < (b) ? (a) : (b))#define MAX_SIZE 100int cmp1(const void* a, const void* b) { int A; sscanf(*(char**) a, \"%d\", &A); int B; sscanf(*(char**) b, \"%d\", &B); return A - B;}int cmp2(const void* a, const void* b) { char* A = *((char**) a); char* B = *((char**) b); char AB[10000] = {\'\\0\'}; strcat(AB, A); strcat(AB, B); char BA[10000] = {\'\\0\'}; strcat(BA, B); strcat(BA, A); return strcmp(AB, BA);}int main() { char line[10000]; gets(line); char* ss[MAX_SIZE]; int ss_size = 0; char* token = strtok(line, \",\"); while(token != NULL) { ss[ss_size++] = token; token = strtok(NULL, \",\"); } qsort(ss, ss_size, sizeof(char*), cmp1); int size = MIN(3, ss_size); qsort(ss, size, sizeof(char*), cmp2); char res[10000]; for(int i=0; i<size; i++) { strcat(res, ss[i]); } puts(res); return 0;}

Java

import java.util.Arrays;import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String[] strs = sc.nextLine().split(\",\"); System.out.println(getResult(strs)); } public static String getResult(String[] strs) { // 按数值大小升序排列 Arrays.sort(strs, (a, b) -> Integer.parseInt(a) - Integer.parseInt(b)); // 取前3个元素（如果数组长度小于3，则取所有元素） String[] tmp = Arrays.copyOfRange(strs, 0, Math.min(3, strs.length)); // 按照拼接结果的字典序排序 Arrays.sort(tmp, (a, b) -> (a + b).compareTo(b + a)); StringBuilder sb = new StringBuilder(); for (String s : tmp) { sb.append(s); } return sb.toString(); }}

Python

import functools# 输入获取strs = input().split(\",\")# 自定义比较函数def cmp(a, b): s1 = a + b s2 = b + a return 0 if s1 == s2 else 1 if s1 > s2 else -1def getResult(strs): # 按数值大小升序排列 strs.sort(key=lambda x: int(x)) # 取前3个元素 tmp = strs[:3] # 按照拼接结果的字典序排序 tmp.sort(key=functools.cmp_to_key(cmp)) return \"\".join(tmp)# 算法调用print(getResult(strs))

复杂度分析

时间复杂度

• 第一次排序： O(n log n) - 按数值大小排序
• 第二次排序： O(k log k)，其中 k = min(3, n) - 按组合规则排序
• 总时间复杂度： O(n log n)

空间复杂度

• 辅助数组： O(k)，其中 k = min(3, n) - 存储选中的元素
• 字符串拼接： O(L)，其中 L 是数字的总长度
• 总空间复杂度： O(n)

结果

通过所有测试用例，算法能够正确处理各种输入情况：

• 数组长度小于3的情况
• 数组长度等于3的情况
• 数组长度大于3的情况

总结

本题是一个典型的贪心算法问题，关键在于：

1. 贪心策略： 选择数值最小的3个元素，保证组成数字的位数最少
2. 排序技巧： 使用自定义比较器，通过字符串拼接比较来确定最优排列
3. 边界处理： 正确处理数组长度小于3的特殊情况

这道题目考查了：

• 贪心算法的应用
• 自定义排序比较器的使用
• 字符串处理技巧
• 边界条件的处理

通过这道题可以加深对贪心算法和排序算法的理解，特别是如何设计合适的比较函数来解决复杂的排序问题。