剑指offer—数组组成的最大最小数 解答

剑指offer—数组组成的最大最小数

题目描述

给定一组非负整数,重新排列它们的顺序使之组成一个最大的整数。

示例 1:

输入: [10,2]
输出: 210
示例 2:
1.最大:
输入: [3,30,34,5,9]
输出: 9534330
2.最小:
例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字为321323。
说明: 输出结果可能非常大,所以你需要返回一个字符串而不是整数。

思路

数组中需要进行排序,但是不是一般的排序,而是按照ab<ba 则推出 a<b,对数组使用这种方式排序,则得到的就是最小的数

例:a=110 b=23 ab=11023 ba=23110 —-> a要放在b前面

代码

  • 最大
class Solution {
    public String largestNumber(int[] nums) {
        List<Long> list = new ArrayList<>();
        for(long num:nums){
            list.add(num);
        }
        Collections.sort(list,new Comparator<Long>(){
            @Override
            public int compare(Long a, Long b) {
                String a1 = a+""+b;
                String b1 = b+""+a;
                if(Long.parseLong(a1)>Long.parseLong(b1)){
                    return -1;
                }
                return 1;
            }
        });
        String re = "";
        for(int m=0;m<nums.length;m++){
            re += list.get(m);
        }
        return re.startsWith("0")?"0":re;
    }
}
  • 最小
public class Solution {
    public String PrintMinNumber(int [] nums) {
        ArrayList<Long> list = new ArrayList<>();
        for(long num:nums){
            list.add(num);
        }
        Collections.sort(list,new Comparator<Long>(){
            @Override
            public int compare(Long a, Long b) {
                String a1 = a+""+b;
                String b1 = b+""+a;
                if(Long.parseLong(a1)>Long.parseLong(b1)){
                    return 1;
                }
                return -1;
            }
        });
        String re = "";
        for(int m=0;m<nums.length;m++){
            re += list.get(m);
        }
        return re.startsWith("0")?"0":re;
    }
}