劍指 Offer 題解：數組拼接最小數字（九度 OJ 1504）

題目描述

給定正整數數組，將所有數字拼接成一個數，求能拼接出的最小數字。例如 `{3, 32, 321} → 321323`。

輸入：多測試用例，每用例先給 n (1≤n≤100)，再給 n 個正整數 (≤10⁷)。
輸出：每用例輸出最小拼接數字。

核心洞察：自定義比較器的排序

**關鍵規則**：對任意兩數字串 `a`、`b`，若 `a+b < b+a`（字典序），則 `a` 應排在 `b` 前面。這保證最終拼接最小。

• 證明：若存在最優排列中 `b` 在 `a` 前且 `a+b < b+a`，交換它們可得更小結果，矛盾。
• 傳遞性：此關係構成嚴格弱序，可用於排序。

算法流程

1. 將所有整數轉為字符串
2. 按上述規則排序（冒泡/快排/庫函數均可）
3. 順序拼接輸出

代碼實現（C 標準庫 qsort 版）

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_N 100
#define MAX_LEN 10  // 10^7 最多 8 位，留餘量

char strs[MAX_N][MAX_LEN];
char cat_a[2*MAX_LEN], cat_b[2*MAX_LEN];

// 比較器：返回 <0 表示 a 排前面
int cmp(const void *a, const void *b) {
    const char *sa = *(const char**)a;
    const char *sb = *(const char**)b;
    strcpy(cat_a, sa); strcat(cat_a, sb);
    strcpy(cat_b, sb); strcat(cat_b, sa);
    return strcmp(cat_a, cat_b);
}

int main() {
    int n;
    while (scanf("%d", &n) == 1 && n > 0 && n <= MAX_N) {
        for (int i = 0; i < n; ++i) {
            int x; scanf("%d", &x);
            sprintf(strs[i], "%d", x);
        }
        // qsort 需要指針數組
        char *ptrs[MAX_N];
        for (int i = 0; i < n; ++i) ptrs[i] = strs[i];
        qsort(ptrs, n, sizeof(char*), cmp);

        // 輸出拼接
        for (int i = 0; i < n; ++i) printf("%s", ptrs[i]);
        printf("\n");
    }
    return 0;
}

原作者冒泡排序版本分析

// 原代碼核心邏輯
void bubbleSort(char c[][10], int n) {
    for (int i = n-1; i > 0; --i)
        for (int j = n-1; j > n-1-i; --j)
            if (findSmall(c, j)) swap(c, j, j-1);
}

int findSmall(char c[][10], int i) {
    // 比較 c[i] + c[i-1] vs c[i-1] + c[i]
    // 字符串拼接後逐字符比較
}

優缺點：邏輯正確，但 O(n²) 在 n=100 時尚可（10⁴ 比較），`qsort` O(n log n) 更優。字符串拼接比較可直接用 `strcmp(strcat(a,b), strcat(b,a))`。

邊界情況與陷阱

測試驗證

複雜度分析

• 時間：O(n log n × k) —— n 個字符串，平均長度 k，比較需拼接 2k
• 空間：O(n × k) —— 存儲字符串數組

總結

本題核心是**識別拼接順序的自定義比較規則**：`a+b < b+a`。將數字轉字符串後按此規則排序，直接拼接即得最小值。工程中優先使用標準庫 `qsort`/`std::sort` 配合自定義比較器，代碼簡潔且性能優於手寫冒泡。注意大數輸出直接流式打印，避免溢出。