剑指 Offer 45. 把数组排成最小的数 (opens new window)

1.枚举+排序

分析：非常有意思的一道题目。最终结果就是将数组两两排序交换位置后，数组拼接成的字符串。本质上就是一种暴力枚举。这里我们转换一种思维方式来看这个问题，应该如何选出放在最低位的数？这里假定这个数为a，那么既然它放在最低位，就说明a与剩下每个数(这里用b代替)拼接组合后，都有ab>ba，所以才把它放在最后面。

所以只需要按照排序规则，每轮枚举出最大的数，那么这个数肯定是放在最后面。

排序规则：ab<ba那么a小于b。

2.错解

😭😭😭个别用例不能通过222/224：[824,938,1399,5607,6973,5703,9609,4398,8247]，对于824和8247两个数排序有误。仅分享思路。

每次取出”最小“的数，最小指的是从左往右比较，当前位置上的数最小则退出返回。比如30和31，十位上3相同那么比较个位，0小于1，所以30”小于“31。而对于数位大小不同的两个数之间比较时例如824和82475，将位数更小的数用个位数补齐，因此转化成82444与82475进行比较。

改进：上述补齐规则应该变成，从另一个数高位开始进行补齐。也就是说824补齐为82482(从82475高位开始取)。从而转化为ab与ba的比较问题。

class Solution {
    public String minNumber(int[] nums) {
        String res="";

        for(int k=0;k<nums.length;k++){
           int head=9,index=-1;
           //找到比较时的首元素
            for(int i=0;i<nums.length;i++){
                if(nums[i]>=0){
                    head=nums[i];
                    index=i;
                    break;
                }
            }
            //找到每轮最小值
           for(int i=0;i<nums.length;i++){
               if(nums[i]>=0){
                   int temp=nums[i];
                   //数位比较
                   for(int j=0;j<Math.max(String.valueOf(temp).length(),String.valueOf(head).length());j++){
                        int currnum=String.valueOf(temp).length()<=j?temp%10:String.valueOf(temp).charAt(j)-'0';
                        int headnum=String.valueOf(head).length()<=j?head%10:String.valueOf(head).charAt(j)-'0';
                        if(currnum<headnum){
                            head=temp;
                            index=i;
                            break;
                        }
                        if(currnum>headnum){
                            break;
                        }
                   }
               }
           }
           //得到最小值
           res+=String.valueOf(head);
           nums[index]=-1;
        }
        return res;
    }
}