描述

思路1：数组排序+字符串比较

将int转为字符串

比较A和B的大小，当A+B<B+A时，则认为A<B。

使用Arrays.sort方法排序

public class Solution {
    public String PrintMinNumber(int [] numbers) {
        int len = numbers.length;
        String[] nums = new String[len];
        for(int i = 0; i < len; i++) {
            nums[i] = numbers[i] + "";
        }
        Arrays.sort(nums, (s1, s2) -> (s1 + s2).compareTo(s2 + s1));
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < len; i++) {
            sb.append(nums[i]);
        }
        return sb.toString();
    }
}

思路2：小顶堆排序+取余比较

1. 当两个字符串长度相等时，直接比较即可，例如11<33，23<32
2. 当两个字符串不相等时，可以先补齐，再比较。例如3(333)>32(32)>3211。

public class Solution {
    public String PrintMinNumber(int [] numbers) {
        int len = numbers.length;
        String[] nums = new String[len];
        for(int i = 0; i < len; i++) {
            nums[i] = numbers[i] + "";
        }
        Arrays.sort(nums, (str1, str2) -> {
            int i = 0;
            while(str1.length() != str2.length()) {
                if(str1.length() < str2.length()) {
                    str1 += str1.charAt(i);
                } else {
                    str2 += str2.charAt(i);
                }
                i++;
            }
            return str1.compareTo(str2);
        });
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < numbers.length; i++) {
            sb.append(nums[i]);
        }
        return sb.toString();
    }
}

也可以使用双指针比较每个字符，当短字符遍历完，则从头开始。

使用小顶堆排序

public class Solution {
    public String PrintMinNumber(int [] numbers) {
        PriorityQueue<Integer> queue = new PriorityQueue<>(
            (num1, num2) -> {
                String str1 = num1 + "";
                String str2 = num2 + "";
                int i = 0;
                int j = 0;
                int len1 = str1.length();
                int len2 = str2.length();
                while(i < len1 || j < len2) {
                    //使用取余运算从头开始
                    int tmp = str1.charAt(i % len1) - str2.charAt(j % len2);
                    if(tmp != 0) {
                        return tmp;
                    }
                    i++;
                    j++;
                }
                return 0;
            });
        for(int i = 0; i < numbers.length; i++) {
            queue.offer(numbers[i]);
        }
        StringBuilder sb = new StringBuilder();
        while(!queue.isEmpty()) {
            sb.append(queue.poll());
        }
        return sb.toString();
    }
}

思路3：全排序

使用回溯法全排列，穷举所有可能的组合。(会超时）

public class Solution {
    public String PrintMinNumber(int [] numbers) {
        dfs(numbers, 0);
        return ret;
    }
    String ret;
    void dfs(int[] nums, int pos) {
        if(pos >= nums.length - 1) {
            StringBuilder sb = new StringBuilder();
            for(int i : nums) {
                sb.append(i);
            }
            if(ret == null) {
                ret = sb.toString();
            } else if(ret.compareTo(sb.toString()) > 0) {
                ret = sb.toString();
            }
        }
        for(int i = pos; i < nums.length; i++) {
            swap(nums, i, pos);
            dfs(nums, pos + 1);
            swap(nums, i, pos);
        }
    }
    void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}