剑指offer - 把数组排成最小的数(Java实现)

题目链接：https://www.nowcoder.com/practice/8fecd3f8ba334add803bf2a06af1b993?tpId=13&&tqId=11185&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

思路一：可以对这个数组进行一个全排列，然后对于每一种情况我们可以进行合并，然后从所有的全排列中找到一种最小值。全排列思路：https://blog.nowcoder.net/n/5f718ef899bf4cea924eeb2bf60fce03。

import java.util.*;

public class Solution {
    static String ans = "";//全局静态变量记录答案
    public String PrintMinNumber(int [] numbers) {
        if(numbers.length == 0) return "";
        int n = numbers.length;
        String[] strs = new String[n];
        for(int i = 0; i < n; ++ i) {
            strs[i] = numbers[i] + "";
        }
        Permutation(0, strs);
        return ans;
    }
    public static void Permutation(int n, String[] strs) {
        if(n == strs.length) {//某种情况成立
            StringBuilder temp = new StringBuilder();
            for(int i = 0; i < n; ++ i) temp.append(strs[i]);
            if(ans.length() != temp.length()) ans = temp.toString();
            if(ans.compareTo(temp.toString()) > 0) {
                ans = temp.toString();
            }
            return ;
        }
        for(int i = n; i < strs.length; ++ i) { //全排列
            Swap(n, i, strs);
            Permutation(n + 1, strs);
            Swap(n, i, strs);
        }
    }
    public static void Swap(int x, int y, String[] strs) {
        String temp = strs[x];
        strs[x] = strs[y];
        strs[y] = temp;
    }
}

思路二：对于这个数组，我们可以按照某种规则进行排序，即：number1 + number2 < number2 + number1，在证明的时候，我们可以任意颠倒两个数字的位置

$A_{1}A_{2}A_{3}....A_{x}A_{x+1}....A_{n}$

$A_{1}A_{2}A_{3}....A_{x+1}A_{x}....A_{n}$
按照我们的排序规则则有 $A_{x}A_{x+1} < A_{x+1}·A_{x}$ , 所以我们的排序规则是成立的。

import java.util.*;
public class Solution {
  public String PrintMinNumber(int [] numbers) {
      ArrayList<String> list = new ArrayList<>();
      for(int val : numbers) { //首先将数组转换为list
          list.add(val + "");
      }
      Collections.sort(list, new Comparator<String>() {//对list进行排序
          public int compare(String s1, String s2) {
              return (s1 + s2).compareTo(s2 + s1);
          }
      });
      StringBuilder ans = new StringBuilder();
      for(String str : list) {//直接拼接答案
          ans.append(str);
      }
      return ans.toString();
  }
}