题目分析

我们需要从一个整数数组中选择3个元素，使得这3个元素拼接后能够形成最小的数字。如果数组长度小于3，则直接将所有元素拼接即可。

输入样例
例如输入：21,30,62,5,31

在这里，我们可以选择21、30、5来拼接成最小的数字，输出结果为21305。

解题思路

1. 解析输入

输入是一行由逗号分隔的整数字符串，例如21,30,62,5,31。我们需要将字符串分割成单独的数字，并将它们存储在一个列表或数组中。

2. 排序筛选

• 先对数组进行从小到大的排序，使得最小的数字排在最前面，确保数位小的排在前面，这样结果才能达到最小。

3. 字典序拼接排序

• 在选出了3个数字后，我们需要按“字典序”进行拼接排序。这是因为，直接将三个数字按从小到大的顺序拼接，并不一定能得到最小的组合。例如，对于"3"和"30"，将"3"放在前面会比"30"放在前面更大，因此需要特别排序。

• 为此，我们定义一种自定义的比较方式：比较两个数字的拼接结果的大小。

• 对于任意两个数字a和b，如果拼接a + b的结果小于拼接b + a的结果，就让a排在b的前面。

• 例如：对于"3"和"30"，因为"303"小于"330"，所以让"30"排在"3"的前面。

复杂度分析

• 时间复杂度：主要的时间开销在于排序，排序的时间复杂度是O(n log n)，其中n是数组的长度。
• 空间复杂度：由于存储了输入的字符串数组，所以空间复杂度为O(n)。

代码实现

C++

#include <bits/stdc++.h> 
using namespace std;

int main() {
    // 读取输入字符串
    string s;
    cin >> s;

    // 使用stringstream分割字符串
    stringstream ss(s);
    string token;
    vector<string> nums;

    while (getline(ss, token, ',')) {
        nums.emplace_back(token);  // 将分割的数字存入nums
    }

    // 按照数值大小排序
    sort(nums.begin(), nums.end(), [](string a, string b) {
        return stoi(a) < stoi(b);
    });

    // 如果元素数量超过3个，保留前3个最小元素
    if (nums.size() > 3) {
        nums.resize(3);
    }

    // 按拼接顺序排序，形成最小数字
    sort(nums.begin(), nums.end(), [](string a, string b) {
        return (a + b) < (b + a);
    });

    // 输出结果
    for (string &num: nums) {
        cout << num;
    }

    return 0;
}

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String input = scanner.nextLine();
        String[] numStrings = input.split(",");

        List<String> nums = new ArrayList<>(Arrays.asList(numStrings));

        // 按数值排序
        nums.sort(Comparator.comparingInt(Integer::parseInt));

        // 选择最小的3个元素，如果长度不足3则选所有
        if (nums.size() > 3) {
            nums = nums.subList(0, 3);
        }

        // 按拼接顺序排序，形成最小数字
        nums.sort((a, b) -> (a + b).compareTo(b + a));

        // 拼接输出结果
        StringBuilder result = new StringBuilder();
        for (String num : nums) {
            result.append(num);
        }
        System.out.println(result.toString());
    }
}

Python

# 导入所需模块
from functools import cmp_to_key

# 自定义比较函数，用于按拼接顺序排序
def compare(a, b):
    if a + b < b + a:
        return -1
    elif a + b > b + a:
        return 1
    else:
        return 0

# 读取输入
s = input().strip()
nums = s.split(',')

# 按数值大小排序
nums.sort(key=int)

# 选择最小的3个元素
if len(nums) > 3:
    nums = nums[:3]

# 按拼接顺序排序
nums.sort(key=cmp_to_key(compare))

# 输出结果
print("".join(nums))

题目描述

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