LeetCode刷题【剑指 Offer 45】把数组排成最小的数

输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

示例 1:

输入: [10,2]
输出: "102"

示例 2:

输入: [3,30,34,5,9]
输出: "3033459"

提示:

• 0 < nums.length <= 100

说明:

• 输出结果可能非常大，所以你需要返回一个字符串而不是整数
• 拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0

愣了好久没看懂，反复思考下：堆排序

class Solution {
    final static int [] sizeTable = { 9, 99, 999, 9999, 99999, 999999, 9999999,
            99999999, 999999999, Integer.MAX_VALUE };

    public String minNumber(int[] nums) {
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                int size1 = stringSize(o1);
                int size2 = stringSize(o2);

                int join1 = o1;
                while (size2>0){
                    join1 *= 10;
                    size2--;
                }
                join1 += o2;
                int join2 = o2;
                while (size1>0){
                    join2 *= 10;
                    size1--;
                }
                join2 += o1;
                return join1 - join2;
            }
        });
        for (int num : nums) {
            queue.offer(num);
        }
        StringBuilder sb = new StringBuilder();
        while (!queue.isEmpty()){
            sb.append(queue.poll());
        }
        return sb.toString();
    }


    public int stringSize(int x) {
        for (int i=0; ; i++)
            if (x <= sizeTable[i])
                return i+1;
    }
}