题解 | #把数组排成最小的数#

个人解法

本题采用自定义比较+快速排序的方法解决

主要是自定义比较，这里分为n中可能

1. 3和3这种 无疑相等，谁在前谁在后是一样的

2. 4和321这种，首字符不相等的情况下，首字符小的要在前面，组成3214，而不是4321

3. 3和321这种，首字符相等的情况下，str1先遍历完了，接着将str2接下来的字符与str1的首字符进行比较，依然是小的在前面。最后比较后拼接的结果是3213，而不是3321。同理，如果321在前面，也是这样比较。

代码有点多，没去优化，将就看了哈哈。

public class Solution {

public int compare(String str1, String str2){
    int index=0, len1=str1.length(),len2=str2.length();
    while(index<len1 && index<len2){
        char c1=str1.charAt(index),c2=str2.charAt(index);
        if(c1==c2)
            index++;
        else if(c1>c2)
            return 1;
        else
            return -1;
    }
    //str1先遍历完，str2还没遍历完
    char c1_start = str1.charAt(0);
    while(index<len2){
        if(str2.charAt(index)==c1_start)
            index++;
        else if(str2.charAt(index)<c1_start)
            return 1;
        else
            return -1;
    }
    //str2先遍历完，str1还没遍历完
    char c2_start = str2.charAt(0);
    while(index<len1){
        if(str1.charAt(index)==c2_start)
            index++;
        else if(str1.charAt(index)>c2_start)
            return 1;
        else
            return -1;
    }
    return 0;
}

//快速排序
public void qSort(String[] str,int l,int r){
    //递归终止条件
    if(l>=r) 
        return;
    int left=l, right=r;
    String pivot = str[left];
    while(left<right){
        //从右边往左扫描，找到比pivot小的字符串
        while(compare(str[right],pivot)>=0 && left<right) right--;
        if(left<right)
            str[left] = str[right];
        //从左边往右扫描，找到比pivot大的字符串
        while(compare(str[left],pivot)<=0 && left<right) left++;
        if(left<right)
            str[right] = str[left];
        if(left<=right)
            str[left] = pivot;
    }
    //分别对左右子序列进行快速排序
    qSort(str,l,right-1);
    qSort(str,right+1,r);
}


public String PrintMinNumber(int [] numbers) {
    int len = numbers.length;
    //转成字符串数组
    String[] res = new String[len];
    for(int i=0;i<len;++i){
        res[i] = String.valueOf(numbers[i]);
    }
    //方法一 暴力解法排序 O(n*2)
    for(int i=0;i<len-1;++i){
        for(int j=i+1;j<len;++j){
            if(compare(res[i],res[j])>0){
                String temp = res[i];
                res[i] = res[j];
                res[j] = temp;
            }
        }
    }

    //方法二 快速排序 O(nlogn)
    qSort(res,0,len-1);
    String ans = "";
    for(String s:res){
        ans += s;
    }
    return ans;
}

}