我如何操纵一个数组以得到最大的数字？

Question

假设您有一个正整数数组，请对其进行处理，以使结果数组的整数串联成为可能的最大数。例如：{9,1,95,17,5}，结果：9951571

作业警察：这是一个Google电话面试问题，未签署任何保密协议;）。

Answer 1

正如其他人指出的那样，按字典顺序排序和连接是很接近的，但并不完全正确。例如，对于数字5，54和56字典编排，将产生 {5，54，56}
（以递增顺序）或 {56，54，5} （以递减顺序），但是我们真正想要的是 {56，5 ，54} ，因为这会产生尽可能多的数字。

因此，我们需要两个数字的比较器，以某种方式将最大的数字放在第一位。

1. 我们可以通过比较两个数字中的单个数字来做到这一点，但是如果另一个数字仍然有剩余数字，则在离开一个数字的结尾时必须格外小心。我们必须弄清许多计数器，算术和边缘情况。

2. 一个更可爱的解决方案（也由@Sarp Centel提到）实现了与（1）相同的结果，但代码却少得多。这个想法是 将两个数字的级联与这些数字的反向级联 进行 比较 。我们必须在（1）中显式处理的所有杂项都是隐式处理的。

例如，比较56和5，我们会做的一个普通字典的比较565来556。由于565>
556，我们将说它56大于5，并且应该排在第一位。同样，进行比较54和5意味着我们将测试545<
554，这表明我们5比更大54。

这是一个简单的例子：

// C++0x: compile with g++ -std=c++0x <filename>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

int main() {
  std::vector<std::string> v = {
    "95", "96", "9", "54", "56", "5", "55", "556", "554", "1", "2", "3"
  };
  std::sort(v.begin(), v.end(),
      [](const std::string &lhs, const std::string &rhs) {
        // reverse the order of comparison to sort in descending order,
        // otherwise we'll get the "big" numbers at the end of the vector
        return rhs+lhs < lhs+rhs;
      });

  for (size_t i = 0; i < v.size(); ++i) {
    std::cout << v[i] << ' ';
  }
}

运行时，此代码显示：

9 96 95 56 556 5 55 554 54 3 2 1