博文中会简要介绍Leetcode P0173题目分析及解题思路。
“Largest Number”这道题比较基础，核心思路是排序。这道题最终是排序，但是关键在于构造出一个可以得到正确结果的比较器，即如何排序，两个数之间如何比较。
Given a list of non-negative integers nums, arrange them such that they form the largest number.
Note: The result may be very large, so you need to return a string instead of an integer.
关于比较方法，我们可以观察下述例子得出，
首先观察下面三个数，
982 432 784
对于这两个数，我们很容易知道应当把982放在784前面，把784放在432前面，从而构造出最大的数。
然后我们再观察下面三个数，
3 34 32
不难发现，我们的排列顺序应当是34、3和32，此时这三个数开头一致，但是由于34的第二位更大，34应当放在前面；对于3和32而言，332显然会大于323，所以应当先选3然后是32。
其实在例子中我们已经运用了比较方法，我们将3和32拼接分别得到332和323，通过比较拼接后的数的大小我们得出3应当排在32前面，即3应当优先被选择。同理第一个例子也可以这么做。
所以最终的比较方法就是任意给定的两个数，对其进行两种不同顺序的拼接，得到两个数分别是数a和数b，然后比较a和b的大小来得到原数的排列顺序。
以下是Java的题解代码实现。
class Solution {
public String largestNumber(int[] nums) {
boolean areAllZeros = true;
for (int num: nums) {
if (num != 0) {
areAllZeros = false;
break;
}
}
if (areAllZeros)
return "0";
List<String> sorted = Arrays.stream(nums)
.boxed()
.map(n -> n.toString())
.sorted((n1, n2) -> {
String res1 = n1+n2;
String res2 = n2+n1;
return res2.compareTo(res1);
})
.collect(Collectors.toList());
StringBuilder result = new StringBuilder();
sorted.forEach(num -> result.append(num));
return result.toString();
}
}
以下是C++的题解代码实现。
class Solution {
public:
string largestNumber(vector<int>& nums) {
bool all_zeros = true;
for (int num: nums) {
if (num != 0) {
all_zeros = false;
break;
}
}
if (all_zeros)
return "0";
sort(nums.begin(), nums.end(), [](int n1, int n2) -> bool {
string num1 = to_string(n1);
string num2 = to_string(n2);
return num2+num1 < num1+num2;
});
string result = "";
for_each(nums.begin(), nums.end(), [&result](int n) {
result += to_string(n);
});
return result;
}
};