劍指offer 面試33 把數組排成最小的數

輸入一個正整數數組，把數組裡所有數字拼接起來排成一個數，列印能拼接出的所有數字中最小的一個，

例如輸入數組 {3, 32, 321}，則列印出這 3 個數字能排成的最小數字 321323。

package algorithm.foroffer.top40;

import java.util.*;

/**
 * Created by liyazhou on 2017/5/30.
 * 面試題33：把數組排成最小的數
 *
 * 題目：
 *      輸入一個正整數數組，把數組裡所有數字拼接起來排成一個數，列印能拼接出的所有數字中最小的一個，
 *      例如輸入數組 {3, 32, 321}，則列印出這 3 個數字能排成的最小數字 321323。
 *
 * 考查點：
 *      1. 字元串排序，// 字典順序排序（字典序順序排序，字典序逆序排序）
 *      2. 比較器
 *
 * 思路：
 *      1. 将數組中所有的整數轉換為字元串
 *      2. 比較兩個字元串A、B的大小（誰排在前，誰排在後）的原則：
 *         比較 A+B 和 B+A，讓兩者按字典序排序的準則，傳回大小值（後驗），
 *         A、B 依據傳回的結果進行排序
 */
public class Test33 {

    public static void cancatMinNumber(int[] array){
        List<String> dictOrderList = new LinkedList<>();
        for (int element: array)
            dictOrderList.add(element + "");

        Collections.sort(dictOrderList, new Comparator<String>(){
            @Override
            public int compare(String o1, String o2) {
                return (o1+o2).compareTo(o2+o1);
            }
        });
        for (String num: dictOrderList)
            System.out.print(num);
    }

    public static void main(String[] args){
        int[][] arrays = {
                {, , },
                {, , },
        };
        for(int[] array: arrays){
            System.out.println(Arrays.toString(array));
            cancatMinNumber(array);
            System.out.println();
        }
    }

}
           

和以上大緻相同的解法。

（2017-8-15 10:12:35）

import java.util.*;
public class Solution {
    public String PrintMinNumber(int [] numbers) {
        // List<Integer> list = Arrays.asList(numbers);
        Integer[] array = new Integer[numbers.length];
        for(int i = ; i < numbers.length; i ++)
            array[i] = numbers[i];

        Comparator<Integer> cmp = new Comparator<Integer>(){
            @Override
            public int compare(Integer t1, Integer t2){
                int num1 = Integer.valueOf("" + t1 + t2);  // 代表t1放在前面
                int num2 = Integer.valueOf("" + t2 + t1);  // 代表t2放在前面
                int result = ;
                if (num1 > num2) result = ;               // 升序排序，t1+t2較大，則t1放後面
                else if (num1 < num2) result = -;         // 升序排序，t1+t2較小，則t1放前面
                return result;
            }
        };
        Arrays.sort(array, cmp);
        StringBuilder s = new StringBuilder();
        for (int i = ; i < array.length; i ++)
            s.append(array[i]);
        return s.toString();
    }
}