如何修改贪心算法代码，实现任意正整数集合的最大拼接数？

你的核心问题在于原代码使用了普通整数大小的排序逻辑，这只适用于单个数字的场景。对于多位数，正确的排序规则应该是：对两个数字a和b，比较a拼接b的结果与b拼接a的结果，哪个更大就把哪个放在前面。比如2和21，221 > 212，所以2应该排在21前面。以下是具体修改步骤：

1. 实现IsGreaterOrEqual核心比较函数 #

这个函数用来判断a拼接b的结果是否大于等于b拼接a的结果。推荐用字符串拼接的方式（避免整数溢出风险），也可以用数值计算的方式（适合数字范围较小的场景）：

方式一：字符串拼接比较（无溢出风险） #

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

// 判断a拼接b的结果是否大于等于b拼接a的结果
int IsGreaterOrEqual(int a, int b) {
    char ab[20], ba[20]; // 预留足够空间存储拼接后的字符串
    sprintf(ab, "%d%d", a, b);
    sprintf(ba, "%d%d", b, a);
    return strcmp(ab, ba) >= 0;
}

方式二：数值拼接比较（注意溢出） #

如果确定输入数字不会过大，也可以用数值计算：

#include <math.h>

// 计算数字的位数
int getDigits(int num) {
    int count = 0;
    if (num == 0) return 1;
    while (num > 0) {
        count++;
        num /= 10;
    }
    return count;
}

// 判断a拼接b的结果是否大于等于b拼接a的结果
int IsGreaterOrEqual(int a, int b) {
    long long ab = (long long)a * pow(10, getDigits(b)) + b;
    long long ba = (long long)b * pow(10, getDigits(a)) + a;
    return ab >= ba;
}

2. 修改选择排序的逻辑 #

原排序是按整数升序排列，现在要改成自定义规则的降序排序：遍历数组时，找到当前未排序部分中「拼接后结果最大」的元素，交换到当前位置。

void swap(int* xp, int* yp) {
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}

void selectionSort(int arr[], int n) {
    int i, j, max_idx; // 改为寻找自定义规则下的"最大"元素

    for (i = 0; i < n - 1; i++) {
        max_idx = i;
        for (j = i + 1; j < n; j++) {
            // 如果arr[j]和arr[max_idx]拼接后，arr[j]在前的结果更大，更新max_idx
            if (!IsGreaterOrEqual(arr[max_idx], arr[j])) {
                max_idx = j;
            }
        }
        swap(&arr[max_idx], &arr[i]);
    }
}

3. 修正main函数中的错误 #

• 移除无效的赋值操作（selectionSort是void类型，不能赋值）
• 直接用输入的n作为数组长度，无需多余的size计算
• 排序后直接遍历输出即可

int main() {
    int n;
    scanf("%d", &n);
    int ints[n];

    for (int i = 0; i < n; i++) {
        scanf("%d", &ints[i]);
    }

    selectionSort(ints, n);

    // 特殊情况处理：如果所有元素都是0，输出0而非000...
    if (ints[0] == 0) {
        printf("0\n");
        return 0;
    }

    // 输出拼接结果
    for (int i = 0; i < n; i++) {
        printf("%d", ints[i]);
    }
    printf("\n");

    return 0;
}

测试示例 #

输入：

2
2 21

输出：221

输入：

3
3 30 34

输出：34330

内容的提问来源于stack exchange，提问作者Chandler Bong