如何操作一个数组，使人数最多？ [英] How can I manipulate an array to make the largest number?

问题描述

假设你有正整数数组，操纵它们，这样得到的数组的整数的级联数量最多的是可能的。 例如：{9,1,95,17,5}，结果是：9955171

Say you have an array of positive integers, manipulate them so that the concatenation of the integers of the resultant array is the largest number possible. Ex: {9,1,95,17,5}, result: 9955171

作业警察：这是一个谷歌手机的面试问题，没有新发展区签署;）

Homework police: This was a google phone interview question and no NDAs were signed ;).

推荐答案

正如其他人所指出的那样，一个字典排序和串联是接近，但并不完全正确。例如，对于数字 5 ， 54 和 56 词典式排序将产生的 {5，54，56} （顺序递增）或 {56，54，5} （按递减顺序），但我们真正要的是 {56，5，54} ，因为这会产生数量最多的可能。

As others have pointed out, a lexicographic sort and concatenation is close, but not quite correct. For example, for the numbers 5, 54, and 56 a lexicographic sort will produce {5, 54, 56} (in increasing order) or {56, 54, 5} (in decreasing order), but what we really want is {56, 5, 54}, since that produces the largest number possible.

因此​​，我们要比较的两个数字，不知怎的，首先将其最大的数字。

So we want a comparator for two numbers that somehow puts the biggest digits first.

1. 我们可以做到这一点通过比较个别的两个数的数字，但我们有，当我们走下的一个数字结束时，如果对方号码仍然剩下的数字要小心。有很多柜台，算术和边缘的情况下，我们必须正确的。

2. 一个可爱的解决方案（也@Sarp Centel提到）达到相同的结果（1），但少了很多code。这样做是为了与这些数字的的反向串联比较两个数的串联。所有的克鲁夫特的，我们必须在（1）隐式地处理显式处理。

1. We can do that by comparing individual digits of the two numbers, but we have to be careful when we step off the end of one number if the other number still has remaining digits. There are lots of counters, arithmetic, and edge cases that we have to get right.

2. A cuter solution (also mentioned by @Sarp Centel) achieves the same result as (1) but with a lot less code. The idea is to compare the concatenation of two numbers with the reverse concatenation of those numbers. All of the cruft that we have to explicitly handle in (1) is handled implicitly.

例如，要比较 56 和 5 ，我们会做一个普通字典比较 565 到 556 。由于 565 > 556 ，我们会说 56 比 5 做大，而应是第一位的。同样地，在比较 54 和 5 意味着我们将测试 545 ＆LT; 554 ，它告诉我们， 5 比 54 。

For example, to compare 56 and 5, we'd do a regular lexicographic comparison of 565 to 556. Since 565 > 556, we'll say that 56 is "bigger" than 5, and should come first. Similarly, comparing 54 and 5 means we'll test 545 < 554, which tells us that 5 is "bigger" than 54.

下面是一个简单的例子：

Here's a simple example:

// 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] << ' ';
  }
}

在运行时，此code显示：

When run, this code displays:

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

这篇关于如何操作一个数组，使人数最多？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！