给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。
https://leetcode-cn.com/problems/largest-number/
注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。
示例1：
输入：nums = [10,2]
输出："210"
示例2：
输入：nums = [3,30,34,5,9]
输出："9534330"
示例3：
输入：nums = [1]
输出："1"
示例4：
输入：nums = [10]
输出："10"
提示：
1 <= nums.length <= 100
0 <= nums[i] <= 109
Java解法
思路：
- 最大数即最大的数字在前方排列
- 每次挑选第一位数最大即可，优先个位数，若有相同多位数字对第二位做同样操作
- 傻逼了，34 比 3 要优先选择参考官方解
package sj.shimmer.algorithm.m4_2021;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Stack;
/**
* Created by SJ on 2021/4/15.
*/
class D78 {
public static void main(String[] args) {
System.out.println(largestNumber(new int[]{10,2}));
System.out.println(largestNumber(new int[]{3,30,34,5,9}));
}
public static String largestNumber(int[] nums) {
int n = nums.length;
// 转换成包装类型，以便传入 Comparator 对象（此处为 lambda 表达式）
Integer[] numsArr = new Integer[n];
for (int i = 0; i < n; i++) {
numsArr[i] = nums[i];
}
Arrays.sort(numsArr, (x, y) -> {
long sx = 10, sy = 10;
while (sx <= x) {
sx *= 10;
}
while (sy <= y) {
sy *= 10;
}
return (int) (-sy * x - y + sx * y + x);
});
if (numsArr[0] == 0) {
return "0";
}
StringBuilder ret = new StringBuilder();
for (int num : numsArr) {
ret.append(num);
}
return ret.toString();
}
public static String largestNumber2(int[] nums) {
if (nums == null||nums.length==0) {
return "";
}
StringBuilder builder = new StringBuilder();
HashMap<Integer, List<Integer>> map = new HashMap<>();
for (int num : nums) {
int temp = num;
while (temp/10>0) {
temp= temp/10;
}
int key = temp % 10;
List<Integer> list = map.getOrDefault(key, new ArrayList<>());
list.add(num);
map.put(key, list);
}
for (int i = 9; i >= 0; i--) {
List<Integer> list = map.get(i);
if (list != null&&list.size()>0) {
int[] array = list.stream().mapToInt(Integer::valueOf).toArray();
Arrays.sort(array);
int digts = 0;
Stack<Integer> stack = new Stack<>();
for (int j = 0; j < array.length; j++) {
if (array[j]>digts*10&&array[j]<(digts+1)*10) {
stack.add(array[j]);
}else {
while (!stack.isEmpty()) {
builder.append(stack.pop());
}
stack.add(array[j]);
digts++;
}
}
while (!stack.isEmpty()) {
builder.append(stack.pop());
}
}
}
return builder.toString();
}
}
image
官方解
https://leetcode-cn.com/problems/largest-number/solution/zui-da-shu-by-leetcode-solution-sid5/
-
排序
比较两个数不同的拼接顺序的结果，进而决定它们在结果中的排列顺序 ，我思考的太复杂了
时间复杂度：O(nlognlogm)
空间复杂度：O(logn)
