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

迷南。 2022-02-20 03:57 190阅读 0赞

## 题目描述 ##

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组\{3，32，321\}，则打印出这三个数字能排成的最小数字为321323。

解题思路—**使用双循环**：这个题目最主要的是要找到题目突破口：**动态比较不同字符串拼接后的大小**。若有两个数字x1和x2，转化为字符串s1和s2，先将它们拼接起来，比较s1+s2和s2+s1的大小，**若s2+s1>s1+s2，则s2应该放到s1的前面**。可以使用双循环，嵌套遍历数组，根据字符串拼接的大小调整数组中数字的位置。  
解题思路—**使用Comparator**：这个方法使用了**Collections中的sort函数**，并且自定义了**Comparator接口**，代码看上去更加简洁明了。**推荐！**

## Java解题—使用双循环 ##

public class Solution {
        public String PrintMinNumber(int [] numbers) {
            if(numbers.length==0)
                return ("");
            String str = "";
            for(int i=0;i<numbers.length;i++)
                for(int j=i+1;j<numbers.length;j++){
                    String str1 = numbers[i] + "" + numbers[j];
                    String str2 = numbers[j] + "" + numbers[i];
                    if(str1.compareTo(str2)>0)
                        swap(numbers, i, j);
                }
            for(int k:numbers)
                str += k;
    
            return str;
        }
        
        public void swap(int[] input, int i, int j){
            int temp = input[i];
            input[i] = input[j];
            input[j] = temp;
        }
    }

## Java解题—使用Comparator ##

import java.util.ArrayList;
    import java.util.Collections;
    import java.util.Comparator;
    public class Solution {
        public String PrintMinNumber(int [] numbers) {
            if(numbers.length==0)
                return ("");
            StringBuilder str = new StringBuilder();
            ArrayList<String> list = new ArrayList<>();
            for(int n:numbers)
                list.add(String.valueOf(n));
            Collections.sort(list, new Comparator<String>() {
                @Override
                public int compare(String o1, String o2) {
                    String s1 = o1 + o2;
                    String s2 = o2 + o1;
                    return s1.compareTo(s2);
                }
            });
            
            for(String s:list)
                str.append(s);
    
            return str.toString();
        }
    }