由数组组成的最大数（理解解决方案）

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

代码中所做的是，

输入数组
降序排列
输出它

输入输出部分简单易懂。

现在使用接受比较函数的 qsort 完成排序。在代码中，虽然该函数名为 swap，但它实际上是一个比较函数 - returns 1 当第一个元素大于第二个元素时。否则 returns 0。像 is 54 > 45? 和 is 45>54?

现在，为什么降序排序会给出应有的输出？让我们看一个例子：

54 > 45 ，这意味着如果大数字在左边，则数字更大。降序排序保留较大的数字。

Answer 2

这完全符合您的描述：

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从哪里来？它是 34 的位数的 10 次方。为了得到位数，我们计算 34 的以 10 为底的对数并将其四舍五入。

所以：

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

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

第二行以相反的顺序对变量做同样的事情（计算 YX 串联）。

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

if (a < b) return 1;

编辑

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

if (n1 == 0) return 1;

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

基本上，比较器中的结果是 "Put n2 first if n1 is 0,"，总是正确的。（我不是 100% 确定为什么需要它。）

Answer 3

假设数组 arr[] 是您问题的解决方案，即其元素的排列方式可产生最大结果 M。因此，交换任意数组元素 i 和 j 不会产生大于 M.

的结果

考虑比较器函数 swap 中的任意索引 i 和 j，以及它们周围的数字：

XXXXXXXX IIIIII XXXXXXXXXXXXXXXX JJJJJJ XXXXXXXXX
-------- ------ ---------------- ------ ---------
arr[...] arr[i]     arr[...]     arr[j]  arr[...]

请注意，如果 IIIIII 块在 JJJJJJ 块之前排序，它将继续在它前面排序，而不管 X 块的内容。因此，当使用此比较对整个数组进行排序时，单独比较 arr 的各个元素会产生最佳解决方案。

您的比较器实现使用 "decimal shifting" 执行此逻辑：如果您想在 y 的数字后面添加 x 的数字，您需要十进制移位 y按 x 中的位数。 x中的位数可以确定为log₁₀(x)；通过将 y 乘以 10^k.

实现十进制左移 k 个位置

注：这一行

if (n1 == 0) return 1;

应该在顶部，在你调用十进制对数之前。应该还有另一行

if (n2 == 0) return 0;

以确保我们不会将零传递给 log10。

Answer 4

您已经很好地解释了您发布的代码为何有效。但是，应该注意的是，只要任何数字的十进制移位版本超过可表示的最大值 int，此方法就会发生溢出。如果我们假设一个 32 位 int 那么它有 10 个数字 (2147483647)，因此比较相对较小的数字（例如 32412 和 12345）会导致问题。

作为替代方案，我们可以使用递归函数直接比较数字。设两个数为n1和n2，分别为d1和d2位数。我们的比较函数需要处理三种情况：

如果d1 == d2我们直接比较n1和n2，例如345 和 463
如果 d1 < d2 我们将 n1 与 n2 的 d1 高位数字进行比较，例如对于 37 和 398，我们比较 37 和 39。如果它们相等，我们递归地比较 n1 和 n2 的 d2-d1 低位数字。因此，对于 37 和 378，我们将比较 37 和 8。
如果 d1 > d2 我们可以交换 n1 和 n2 并按照情况 2 进行比较，尽管我们必须颠倒结果的顺序。

这里有一些代码来说明。

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

   int d1 = numDigits(n1);
   int d2 = numDigits(n2);
   return compare0(n1, d1, n2, d2);
}

int compare0(int n1, int d1, int n2, int d2)
{
    if (d1 == d2)
        return n2 - n1;
    else if (d1 < d2)
        return  compare1(n1, d1, n2, d2);
    else
        return -compare1(n2, d2, n1, d1);
}

int compare1(int n1, int d1, int n2, int d2)
{
    int pd = (int) pow(10, d2 - d1);
    int nh2 = n2 / pd;
    if (n1 == nh2)
        return compare0(n1, d1, n2 % pd, d2 - d1);
    else
        return nh2 - n1;
}

int numDigits(int n)
{
    return (n == 0) ? 1 : 1 + (int) log10(n);
}

由数组组成的最大数（理解解决方案）

Largest number formed from an array (understanding a solution)

arrays

sorting

algorithm

quicksort