把数组排成最小的数

文章目录

1. 1. 题目
2. 2. 解析
3. 3. 代码
4. 4. 参考

题目

输入一个正整数数组，将它们连接起来排成一个数，输出能排出的所有数字中最小的一个。例如输入数组{32,  321}，则输出这两个能排成的最小数字32132。请给出解决问题的算法，并证明该算法。

解析

假如有两个数字a,b，其关键思路不是比较a,b，而是比较ab和ba。。。
如果ab<ba,则会有a<b，所以这题的关键就是构建a,b的比较器

不得不说，这个思路太妙了^_^

关于证明：请看这个

代码

/** * 思路是比较ab和ba。。。如果ab<ba,则会有a<b * @param a * @return */
 * 思路是比较ab和ba。。。如果ab<ba,则会有a<b
 * @param a
 * @return
 */
public static String minimumCombination(Integer[] a){

	Arrays.sort(a, new Comparator<Integer>(){
		public int compare(Integer a,Integer b)		{
		
			return (a+""+b).compareTo(b+""+a);//构建ab的比较器
		}
	});
	
	StringBuilder sb=new StringBuilder();
	for(int i=0;i<a.length;i++)
	{
		sb.append(a[i]);//然后直接连起来就可以了
	}
	
	return sb.toString();
	
}

测试代码

public static void main(String[] args) {
	Integer[] a={32,321,23}; 
	System.out.println(minimumCombination(a));

}

输出

2332132

参考

• July 微软面试100题系列 第68题
• 【百度面试题】把数组排成最小的数

---

本作品采用[知识共享署名-非商业性使用-相同方式共享 2.5]中国大陆许可协议进行许可，我的博客欢迎复制共享，但在同时，希望保留我的署名权