剑指offer-32、把数组排成最⼩的数

题⽬描述

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

示例1 输⼊：[3,32,321] 返回值："321323"

思路及解答

自定义排序（推荐解法）

这道题要求拼起来的数是最⼩的数字，其实是⼀个排序问题，只要理解了这⼀点，就可以快速解决。

假设有两个字符串 s1=3 ， s2=32 ，那 s1+s2=332 , s2+s1=323 ,也就是 s1+s2>s2+s1 。

像上⾯这种情况，要想拼接起来的数最⼩，肯定是 s2 在前⾯， s1 在后⾯。

⽽在数组中，我们要使所有的拼接起来是最⼩，则需要两两⽐较，类似排序，把满⾜ s1+s2>s2+s1 的s1 放到后⾯， s2 放到前⾯。

public class Solution {

	public String PrintMinNumber(int [] numbers) {
		String[] strs = new String[numbers.length];
		for(int i = 0; i < numbers.length; i++)
			strs[i] = String.valueOf(numbers[i]);
		
		Arrays.sort(strs, (x, y) -> (x + y).compareTo(y + x));
		StringBuilder res = new StringBuilder();
		for(String s : strs)
			res.append(s);
		return res.toString();
	}

}

• 时间复杂度 : O(nlogn) , n 为 nums 数组的⻓度，使⽤内置排序函数的平均时间复杂度为O(nlogn) ，最差为 O(n2 ) 。
• 空间复杂度: O(N)

手动实现快速排序

我们也可以不依赖内部排序，自己手动实现

public class Solution {
    public String PrintMinNumber(int[] numbers) {
        if (numbers == null || numbers.length == 0) return "";
        
        String[] strs = new String[numbers.length];
        for (int i = 0; i < numbers.length; i++) {
            strs[i] = String.valueOf(numbers[i]);
        }
        
        // 手动实现快速排序
        quickSort(strs, 0, strs.length - 1);
        
        StringBuilder sb = new StringBuilder();
        for (String s : strs) {
            sb.append(s);
        }
        return sb.toString();
    }
    
    private void quickSort(String[] strs, int left, int right) {
        if (left >= right) return;
        
        int pivotIndex = partition(strs, left, right);
        quickSort(strs, left, pivotIndex - 1);
        quickSort(strs, pivotIndex + 1, right);
    }
    
    private int partition(String[] strs, int left, int right) {
        String pivotValue = strs[right];
        int i = left;
        
        for (int j = left; j < right; j++) {
            // 使用自定义比较规则
            if ((strs[j] + pivotValue).compareTo(pivotValue + strs[j]) <= 0) {
                swap(strs, i, j);
                i++;
            }
        }
        swap(strs, i, right);
        return i;
    }
    
    private void swap(String[] strs, int i, int j) {
        String temp = strs[i];
        strs[i] = strs[j];
        strs[j] = temp;
    }
}