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

题目

题目描述

给定一个整型数组，请从该数组中选择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个较小的数字
组合排序： 对选中的数字按照拼接结果的字典序排序
拼接输出： 将排序后的数字拼接成最终结果

排序策略：

关键在于第二步的排序规则：对于两个数字 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 100

int 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 -1

def 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的情况

总结

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

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

这道题目考查了：

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

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

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

文章目录

题目