題目

題目描述

給定一個整型數組，請從該數組中選擇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的特殊情況

這道題目考查了：

• 貪心算法的應用
• 自定義排序比較器的使用
• 字符串處理技巧
• 邊界條件的處理

通過這道題可以加深對貪心算法和排序算法的理解，特別是如何設計合適的比較函數來解決復雜的排序問題。