数组：最大可能的数字

Question

给定一个元素数组，找到使用数组元素可以组成的最大可能数字。
例如：10 9
答案：910
2 3 5 78
答案：78532
100 9
答案：9100

我知道这个问题可以使用自定义字符串比较器来解决，但我不理解它是如何工作的。

    #include <iostream>
    #include <string>
    #include <algorithm>
    #include <vector>

    using namespace std;


    bool compare ( string a, string b )  
    {  
            return atoi( (a+b).c_str() ) < atoi((b+a).c_str() );  
    }

    int main()  
    {  
            vector<string> vs;  
            string s;  
            while ( cin >> s ) {  
                    vs.push_back(s);  
            }  
            sort( vs.begin(), vs.end(), compare );  
            for ( int i = vs.size()-1; i >= 0; i-- ) {  
                    cout << vs[i];  
            }  
    }   

有人能提出一个算法来解决这个问题吗？ 欢迎对上述比较器进行解释。 谢谢

- Pritpal

---

不好的解决方案：nlog(n) 复杂度（排序）加上缓慢的 compare() 函数。 - Gene Bushuyev

@Gene Bushuyev：有更好的复杂度解决方案吗？ - Tugrul Ates

我之前问过这个问题，请查看我的个人资料。有一个很好的答案。 - Kakira

可能是数组操作面试题的重复。 - nos

将以下与编程有关的内容从英语翻译成中文。只返回已翻译的文本：这不是重复...如果我发布了问题，你无论如何都找不到它 - Pritpal

Answer 1

如果我们有两个字符串S和T，最常见的做法是按字典顺序反向连接它们，以使最大的数字排在前面。然而，当其中一个字符串是另一个字符串的前缀时，这种方法并不完全有效。

设T=SA，即S是T的前缀。我们有两种连接选择：SSA和SAS。显然，我们的选择将取决于哪个数字更大：AS还是SA。

下面是修改过的代码，满足此算法：

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;


bool compare ( string a, string b )  
{  
        int i, j;
        for( i = 0; i < a.size() && i < b.size(); ++i )
               if( a[ i ] != b[ i ] )
                     break;
        if( i < a.size() && i < b.size() ) //  if digit mismatch happened
               return a[ i ] < b[ i ];
        if( i == a.size() )                // a is a prefix for b
        {
               string suffix = b.substr( i );
               return a + suffix < suffix + a;
        }
        else                               // b is a prefix for a
        {
               string suffix = a.substr( i );
               return suffix + b < b + suffix;
        }
}

int main()  
{  
        vector<string> vs;  
        string s;  
        while ( cin >> s ) {  
                vs.push_back(s);  
        }  
        sort( vs.begin(), vs.end(), compare );  
        for ( int i = vs.size()-1; i >= 0; i-- ) {  
                cout << vs[i];  
        }  
}

- Grigor Gevorgyan

---

非常好且简洁的解决方案！ - Priyank Bhatnagar

Answer 2

比较器会比较两个字符串，如果组合 a+b 在 b+a 之前或之后。例如，对于输入 a=4; b=3，字符串 "34" 小于 "43"，因此 4 应该在 3 之前。

因此，数字 2 3 5 78 将被排序为 78 5 3 2，因此结果是 78532。

- Howard

Answer 3

按从左到右比较数字的方式，将它们按字典顺序排序。这样做可以使大数字先出现，从而使连接后的数字更大。

编辑：正如Grigor指出的那样，您必须先反转字符串，然后按相反的字典顺序排序，最后连接并反转结果。

- PengOne

---

实际上这并不完全正确，因为在某些情况下它无法奏效，例如： "9" 和 "91"："9" 字典顺序更小，我们将它们连接起来得到 "991"。 但是： "1" 和 "19"："1" 字典顺序更小，但在这种情况下我们需要将它们反过来使用："191" 比 "119" 更大。 - Grigor Gevorgyan

Answer 4

您正在使用比较运算符来查找由两个数字（字符串形式）以可能的两种方式连接而成的两个数字中的较大者，即a+b和b+a。由于您对比较数字的大小感兴趣，因此使用atoi()函数将字符串转换为相应的数字。
但是这种转换并不是必需的。由于a+b和b+a两个字符串的长度相同，按字典顺序比较与数字大小相当。只有在比较的两个字符串的长度不相等时才需要进行转换。

- Terminal

Answer 5

给定一个整数数组，您可以简单地执行多个二分搜索以查找最大的数字。每次执行此操作时，将数字连接到您的字符串（结果）的末尾，并记住排除先前添加的数字。

- user461697