《剑指offer》(三十二)--把数组排成最小的数（java）

考点：时间效率、数组

题目描述

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。

代码格式

import java.util.ArrayList;
public class Solution {
    public String PrintMinNumber(int [] numbers) {

    }
}

解题一-先拼接再排序

1.思路
（1）数组{s1，s2},当比较两个字符串s1, s2大小的时候，先将它们拼接起来；
（2）比较s1+s2,和s2+s1那个大，如果s1+s2大，那说明s2应该放前面，所以按这个规则，s2就应该排在s1前面。
2.代码

import java.util.ArrayList;

public class Solution {
    public String PrintMinNumber(int [] numbers) {
        //判断数组是否为空
        if(numbers == null || numbers.length == 0)
            return "";
       
        for(int i=0; i < numbers.length; i++){
            for(int j = i+1; j < numbers.length; j++){
                 // 先将两个数组拼接起来
                int sum1 = Integer.valueOf(numbers[i]+""+numbers[j]);
                int sum2 = Integer.valueOf(numbers[j]+""+numbers[i]);
                //0然后比较两个数组的大小
                if(sum1 > sum2){
                    int temp = numbers[j];
                    numbers[j] = numbers[i];
                    numbers[i] = temp;
                }
            }
        }
        //定义一个字符串
        String str = new String("");
        for(int i=0; i < numbers.length; i++)
            //最后转化为字符串
            str = str + numbers[i];
        return str;
    }
}

解题二-转化为字符串数组

1.思路
将整型数组转为字符串数组后排好序然后连接起来
2.代码

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

public class Solution {
    public String PrintMinNumber(int [] numbers) {
        ArrayList<String> result = new ArrayList<>();
        for(int i : numbers){
            result.add( i + "" );
        }
 
        Collections.sort(result, new Comparator<String>() {
 
            public int compare(String o1, String o2) {
                int i = 0, j = 0;
                while(i < o1.length() || j < o2.length()){
                    if(j==o2.length()) j-=o2.length();
                    if(i==o1.length()) i-=o1.length();
                    if(o1.charAt(i) < o2.charAt(j)){
                        return -1;
                    }else if(o1.charAt(i) > o2.charAt(j)){
                        return 1;
                    }
                    i++; j++;
                }
                return 0;
            }
        });
 
        StringBuilder stringBuilder2 = new StringBuilder();
        for(String s : result){
            stringBuilder2.append(s);
        }
        return stringBuilder2.toString();
    }
}

1.对于String或Integer这些已经实现Comparable接口的类来说，可以直接使用Collections.sort方法传入list参数来实现默认方式（正序）排序；
2.如果不想使用默认方式（正序）排序，可以通过Collections.sort传入第二个参数类型为Comparator来自定义排序规则；
3.如果想使用Collections.sort的方式一进行排序，可以通过实现Comparable接口的compareTo方法来进行，如果不实现，则参考第2点；
4.jdk1.8的Comparator接口有很多新增方法，其中有个reversed()方法比较实用，是用来切换正序和逆序的，

参考：https://www.nowcoder.com/questionTerminal/8fecd3f8ba334add803bf2a06af1b993?answerType=1&f=discussion