leetcode 179题 最大数
给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。
注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。
示例 1：
输入：nums = [10,2]
输出："210"
示例 2：
输入：nums = [3,30,34,5,9]
输出："9534330"
示例 3：
输入：nums = [1]
输出："1"
示例 4：
输入：nums = [10]
输出："10"
思路
快速排序
代码
/**
* @param {number[]} nums
* @return {string}
*/
var largestNumber = function(nums) {
// 利用快速排序，根据字符的大小来排序
if (nums.length === 0) {
return "";
}
const numStrs = nums.map(item => item+'');
partitionStringSort(numStrs, 0, numStrs.length - 1);
let res = "";
for (let i=0; i<numStrs.length; i++) {
const str = numStrs[i];
if (res === '0') {
continue;
}
res += str;
}
return res;
};
function partition(a, lo, hi) {
const pivot = a[hi];
let i = lo-1;
for (let j=lo; j<hi; j++) {
const ajStr = a[j] + pivot;
const pivotStr = pivot + a[j];
if (ajStr > pivotStr) {
i++;
[a[i], a[j]] = [a[j], a[i]];
}
}
[a[i+1], a[hi]] = [a[hi], a[i+1]];
return i+1;
}
function partitionStringSort(a, lo, hi) {
if (lo >= hi) {
return;
}
const p = partition(a, lo, hi);
partitionStringSort(a, lo, p-1);
partitionStringSort(a, p+1, hi);
}
复杂度分析
- 时间复杂度：O(N^2)
- 空间复杂度：O(N^2)