LeetCode—剑指Offer：把数组排成最小的数（快速排序）

把数组排成最小的数（中等）

2020年9月5日

题目来源：力扣

解题

1.明确两个数之间如何判断大小，可以采用字符串拼接，例如
用"3"、“30"做比较
“3”+“30”>“30”+“3”
“330”>“303”
看出"3”>“30”

2.知道判断方法后，通过两两比对进行排序，这里选择快速排序

class Solution {
    public String minNumber(int[] nums) {
        int len=nums.length;
        //定义一个字符串数组
        String[] str_nums=new String[len];
        //整型数组转字符串数组
        for(int i=0;i<len;i++){
            str_nums[i]=String.valueOf(nums[i]);
        }
        fastSort(str_nums,0,len-1);
        StringBuilder sb=new StringBuilder();
        for(String s:str_nums){
            sb.append(s);
        }
        return sb.toString();
    }
    private void fastSort(String[] str_nums,int l,int r){
        if(l>=r) return;
        int i=l,j=r;
        //记录左边界值
        String tmp=str_nums[i];
        while(i<j){
            //从右往左推，直到找到一个比标记值小的
            while((str_nums[j]+str_nums[l]).compareTo(str_nums[l]+str_nums[j])>=0 && i<j){
                j--;
            }
            //从左往右推，直到找到一个比标记值大的
            while((str_nums[l]+str_nums[i]).compareTo(str_nums[i]+str_nums[i])>=0 && i<j){
                i++;
            }
            //把大小两个值交换位置
            tmp=str_nums[i];
            str_nums[i]=str_nums[j];
            str_nums[j]=tmp;
        }
        str_nums[i]=str_nums[l];
        str_nums[l]=tmp;
        fastSort(str_nums,l,i-1);
        fastSort(str_nums,i+1,r);
    }
}