把数组排成最小的数

2018-04-28

编程练习

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

思路：由题可知，此题的重点在于拼接数字的多种可能性，即对输入的的数组元素需做一个全排列，然后拼接成一个数字，再做比较。

　　整数拼接写起来很麻烦，遂很容易想到将数组元素的各个int值转为String类型，变换成字符串来处理，就变成了字符串的全排列问题，此题之前已经做过，如果通过了那道字符串的全排列问题，这道题就很简单了，只需那道题的排列函数稍加改动，就可以完成此题所需的字符串全排列。做完排列以后需要将结果集中的字符串再转为整数类型，才可调用sort函数来进行整数的排序。

　　注意：因为数组元素个数的不确定性，所以此题不建议用int型来盛装最后的结果集，我一开始用的int,结果后来发现拼接后的数字很有可能超过10位数字，此时int就不够用了，需要改用Long类型。此外，还需考虑输入数组为空和输入数组长度为0的特殊情况，这两者的返回值一个为null,另一个为””。

java代码如下：

import java.util.ArrayList;
import java.util.List;

public class PrintMinNumber {
	public static String PrintMinNumber(int [] numbers) {
		
		if(numbers==null) {
			return null;
		}
		if(numbers.length==0) {
			return "";
		}
		
		ArrayList<String> strlist=new ArrayList<String>();
		ArrayList<String> reslist=new ArrayList<String>();
		ArrayList<Long> longList=new ArrayList<Long>();
		
		for(int i:numbers) {
			String str=String.valueOf(i);
			strlist.add(str);
		}
		//全排列
		pailie(reslist,strlist,0);
		
		//删除重复的序列
    	ArrayList<String> flist=new ArrayList<String>();
    	for(int i=0;i<reslist.size();i++) {
    		String str=reslist.get(i);
    		flist.add(str);
    		List<String> sublist = reslist.subList(i+1, reslist.size());
    		while(sublist.contains(str)) {
    			sublist.remove(str);
    		}
    	}
    	//将字符串list转换成整数List才可以进行大小比较
		for(String s:flist) {
			Long b=Long.parseLong(s);
			longList.add(b);
		}
		//对longlist做从小到大的排序
		longList.sort(null);
		
		//将最小值再转为String格式返回
		return String.valueOf(longList.get(0));
    }
	
	public static void swap(List<String> strlist,int i,int j) {
    	
    	String temp=strlist.get(i);
    	strlist.set(i, strlist.get(j));
    	strlist.set(j, temp);
    }
	/**
	 * 全排列函数
	 * @param list 返回的结果集
	 * @param strlist 参加排序的list
	 * @param start 选定要开始排序的位置
	 */
	public static void pailie(ArrayList<String> list,List<String> strlist,int start) {
    	
    	if(strlist==null) {
    		return;
    	}
    	//先交换，交换后还得换回来，以保证下一次交换时start处位置的字符串是第一次交换时的字符串
		for(int i=start;i<strlist.size();i++) {
			swap(strlist,start,i);
			String tmp="";
			for(int j=0;j<strlist.size();j++) {
				tmp=tmp+strlist.get(j);
			}
			list.add(tmp);
			pailie(list,strlist,start+1);
			swap(strlist,start,i);
		}
    }
	
	
	public static void main(String[] args) {
		
		int [] arr= {3334,3,3333332};
		
		System.out.println(PrintMinNumber(arr));
	}
}