arrays - 我怎样才能操纵一个数组来产生最大的数字？

Question

假设您有一个正整数数组，对它们进行操作，使结果数组的整数串联成为可能的最大数。例如:{9,1,95,17,5}，结果:9955171

作业警察:这是一个谷歌电话面试问题，没有签署保密协议(protocol)；)。

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