假设你有正整数数组,操纵它们,这样得到的数组的整数的级联数量最多的是可能的。 例如:{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.
一个可爱的解决方案(也@Sarp Centel提到)达到相同的结果(1),但少了很多code。这样做是为了与这些数字的的反向串联比较两个数的串联。所有的克鲁夫特的,我们必须在(1)隐式地处理显式处理。
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 < 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更多推荐
如何操作一个数组,使人数最多?
发布评论