Day78 最大数

给定一组非负整数 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/

1. 排序

   比较两个数不同的拼接顺序的结果，进而决定它们在结果中的排列顺序 ，我思考的太复杂了

   • 时间复杂度：O(nlognlogm)

   • 空间复杂度：O(logn)