剑指Offer——把数组排成最小的数

爱被打了一巴掌 2023-01-17 07:49 4阅读 0赞

![转自leetcode剑指Offer][leetcode_Offer]主要思路：  
设数组中任意字符串为x与y，则有：  
若x+y>y+x，则x“大于”y，反之，若y+x>x+y，则y“大于”x，例如字符串"10"与"2"，“10”+“2”=“102”，“2”+“10”=“210”，由于102字典序小于210（String.compareTo()方法比较字符串的大小，ASCⅡ码），则"2"大于"10"拼接字符串时，"2"在"10"的后面，故大体思路为：使用快速排序将字符串从小到大排好后拼接，拼接得到的即为最小的字符串，Java代码如下：

class Solution { 
        public String minNumber(int[] nums) { 
            if(nums.length==0) return new String("");
            String numStr[]=new String[nums.length];
            for(int i=0;i<nums.length;i++){ 
                numStr[i]=String.valueOf(nums[i]);
            }
            quickSort(numStr,0,numStr.length-1);
            StringBuilder res=new StringBuilder();
            for(int j=0;j<numStr.length;j++){ 
                res.append(numStr[j]);
            }
            return res.toString();
        }
        public void quickSort(String numStr[],int left,int right){ 
            if(left>=right) return;
            int i=left,j=right;
            String temp=numStr[left];
            while(i<j){ 
                while((numStr[j]+numStr[left]).compareTo(numStr[left]+numStr[j])>=0&&i<j) j--;
                while((numStr[i]+numStr[left]).compareTo(numStr[left]+numStr[i])<=0&&i<j) i++;
                temp=numStr[i];
                numStr[i]=numStr[j];
                numStr[j]=temp;
            }
            numStr[i]=numStr[left];
            numStr[left]=temp;
            quickSort(numStr,left,i-1);
            quickSort(numStr,i+1,right);
        }
        
    }

[leetcode_Offer]: /images/20221021/9ae39188c340439fbffeff99aa433e9e.png