剑指Offer:面试题33——把数组排成最小的数(java实现)（未完待续）

问题描述：

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

思路1：

最直接的做法就是先求出这个数组中的所有数字的全排列，然后把每个排列拼起来，最后求出i拼起来的数字的最小值。

思路2：

1.找到一种排序规则，数组根据这个排序规则能拍成一个最小的数字比如m与n， mn排起来小于nm排列，则定义mn小于nm

2.其次，要考虑的是如何拼接数字，即给出数字m与n，怎么得到数字mn和nm并比较他们的大小。（直接用数字去计算不难办到，但是要考虑到表达类型与溢出问题）。所以我们直观的选择字符串来表达数字。同时mn与nm的位数肯定是相同的，因此比较它们的大小只需要按照字符串大小的比较规则就可以了。

代码：(哎，没写出来。)

下面别人的代码（先贴出来研究研究）

import java.util.ArrayList;import java.util.List;import java.util.Arrays;public class Solution {String minValue = null;public String PrintMinNumber(int [] numbers) {if(numbers == null || numbers.length == 0)return "";List<Integer> datas = new ArrayList<Integer>();for(int i=0;i<numbers.length;i++){datas.add(numbers[i]);minValue = minValue+numbers[i];}sort(datas, new ArrayList<Integer>(), numbers.length);return String.valueOf(minValue);}public void sort(List<Integer> datas, List<Integer> target, int length){if(target.size() == length){StringBuilder sb = new StringBuilder();for(int i=0;i<target.size();i++){sb.append(target.get(i));}if(sb.toString().compareTo(minValue)<0){minValue = sb.toString();}}for(int i=0;i<datas.size();i++){List<Integer> newDatas = new ArrayList<Integer>(datas);List<Integer> newTarget = new ArrayList<Integer>(target);newTarget.add(newDatas.get(i));newDatas.remove(i);sort(newDatas, newTarget, length);}}}