Code More Create

Appearance

Return to top
On this page

45.把数组排成最小的数

题目

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

代码

TODO注解

class Solution {
    public String minNumber(int[] nums) {
        int len = nums.length;
        String[] strs = new String[len];
        for(int i = 0; i < len; i++){
            strs[i] = String.valueOf(nums[i]);
        }
        quickSort(strs,0,len - 1);
        StringBuffer ans = new StringBuffer();
        for(String str:strs){
            ans.append(str);
        }
        return new String(ans);
    }
    public void quickSort(String[] arr, int l, int r){
        if(r <= l) return;
        int i = l, j = r;
        // 以第一个值作为基准值
        String p = arr[l];
        while(i < j){
        // 这里一定要右边先走，才能保证后续交换基准值的左右两边的值分别小于和大于基准值
            while(i < j && (arr[j] + p).compareTo(p + arr[j]) <= 0 ) j--;
            while(i < j && (arr[i] + p).compareTo(p + arr[i]) >= 0) i++;
            String tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
        // i,j停下的位置，与基准值互换
        arr[l] = arr[i];
        arr[i] = p;
        quickSort(arr,l, j - 1);
        quickSort(arr,j + 1, r);
    }
}