【剑指offer】把数组排成最小的数

看到这个题目，就想到先写一个样例，然后找规律：
{30, 32};
分析：第一位3相同，第二位0在前
{3, 32, 321, 30, 311};
分析：第一位3相同，再分析第二位：第二位没有；第二位比第第一位大时或比第一位小时；第二位相同...
{30, 301, 30301};
分析：前两位相同...

经过一系列简单的分析，就可以找到一个贪心策略，把数组排成最小的数。

// 做题要多看题解，看别人的思路，而不仅仅是AC！

// 通过上述的分析，写了一个递归比较两个数：30,30301
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;

public class Solution {

    public static String PrintMinNumber(int[] numbers) {
        Integer[] nums = new Integer[numbers.length];
        for (int i = 0; i < numbers.length; i++) {
            nums[i] = numbers[i];
        }
        Arrays.sort(nums, new Comparator<Integer>() {
            public int compare(Integer o1, Integer o2) {
                String str1 = Integer.toString(o1);
                String str2 = Integer.toString(o2);
                int minIndex = Math.min(str1.length(), str2.length()), i;
                for (i = 0; i < minIndex; i++) {
                    if (str1.charAt(i) != str2.charAt(i)) {
                        return str1.charAt(i) - str2.charAt(i);
                    }
                }
                if (i == str1.length() && i == str2.length()) {
                    return 1;
                } else if (i == str1.length()) {
                    return compare(o1, Integer.parseInt(str2.substring(i)));
                } else {
                    return compare(Integer.parseInt(str1.substring(i)), o2);
                }
            }
        });
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < nums.length; i++) {
            sb.append(nums[i]);
        }
        return sb.toString();
    }

    public static void main(String[] args) {
//        int[] numbers = {30, 32};
//        int[] numbers = {3, 32, 321, 30, 311};
//        int[] numbers = {30, 301, 30301};
        int[] numbers = {1, 11, 111};
        System.out.println(PrintMinNumber(numbers));
    }
}

看offer书，发现我写的递归，可以进行更简单的改写，nice！

import java.util.Arrays;
import java.util.Comparator;

public class Solution {

    public static String PrintMinNumber(int[] numbers) {
        String[] nums = new String[numbers.length];
        for (int i = 0; i < numbers.length; i++) {
            nums[i] = Integer.toString(numbers[i]);
        }
        Arrays.sort(nums, new Comparator<String>() {
            public int compare(String o1, String o2) {
                String str1 = o1 + o2;
                String str2 = o2 + o1;
                return str1.compareTo(str2);
            }
        });

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < nums.length; i++) {
            sb.append(nums[i]);
        }
        return sb.toString();
    }

    public static void main(String[] args) {
//        int[] numbers = {30, 32};
//        int[] numbers = {3, 32, 321, 30, 311};
//        int[] numbers = {30, 301, 30301};
        int[] numbers = {1, 11, 111};
        System.out.println(PrintMinNumber(numbers));
    }
}