arrays - 由数组形成的最大数字(理解解决方案)

Question

编写一个函数，在给定一个非负整数列表的情况下，对它们进行排列，使它们形成尽可能大的数字。例如，给定 [0, 1, 2, 3]，形成的最大数字是 3210。

我理解的逻辑:

我们比较两个数字 XY(Y 附加在 X 末尾)和 YX(X 附加在 Y 末尾)。如果 XY 较大，则输出中 X 应位于 Y 之前，否则 Y 应位于之前。例如，设 X 和 Y 分别为 542 和 60。为了比较 X 和 Y，我们比较 54260 和 60542。由于 60542 大于 54260，所以我们将 Y 放在前面。我也可以为此编写代码。

令我惊讶的是这个解决方案:

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

int swap(const void *c, const void *d) {
    int n1 = *(int*)c;
    int n2 = *(int*)d;

    int a = pow(10, floor(log10(n2)) + 1) * n1 + n2;
    int b = pow(10, floor(log10(n1)) + 1) * n2 + n1;

    if (n1 == 0) return 1;
    if (a < b) return 1;

    return 0;
}

int main() {
    int t = 0, tc = 0;

    scanf("%d", &t);
    for(tc = 1; tc <= t; tc++) {
        int n;
        scanf("%d",&n);
        int arr[n];

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

        qsort(arr, n, sizeof(int), swap);

        for (int i = 0; i < n; i++)
            printf("%d", arr[i]);
        printf("\n");
    }
    return 0;
}

令我惊讶的是，它通过了所有测试用例。谁能给我解释一下这个逻辑吗？

Answer 1

这正是您所描述的:

int a = pow(10, floor(log10(n2)) + 1) * n1 + n2;
int b = pow(10, floor(log10(n1)) + 1) * n2 + n1;

如果我们传入X和Y，那么a就是XY，而 b 是 YX。

如果您要连接 2 和 34，则需要将 2 乘以 100(得到 200)，然后加上 34(得到 234)。这100是从哪里来的？它是 10 的 34 位数次方。为了获得位数，我们计算 34 以 10 为底的对数并将其向上舍入。

所以:

log10(34) ~= 1.5
floor(log10(34)) == 1
floor(log10(34)) + 1 == 2

10^2 = 100，所以现在我们知道在添加第二个数字之前将第一个数字乘以什么。

第二行以相反的顺序对变量执行相同的操作(计算连接的 YX)。

最后，如果 a < b，我们返回 1，否则返回 0。这使其成为排序函数的工作比较器:

if (a < b) return 1;

编辑

我不确定这条线在做什么:

if (n1 == 0) return 1;

我认为它可能会保护我们免受 log10(0) 结果的影响。 (我不确定返回什么......数学结果是负无穷大。)

基本上，比较器中的结果是“如果 n1 为 0，则将 n2 首先放置”，这总是正确的。 (我只是不是 100% 确定为什么需要它。)