题目

题目描述

给定一个整型数组，请从该数组中选择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 <stdio.h>
#include <stdlib.h>
#include <string.h>#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 + bs2 = b + areturn 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的特殊情况

这道题目考查了：

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

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