By

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

题目

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

解析

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

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

关于证明：请看这个

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 思路是比较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();
	
}

测试代码

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

}

输出

2332132

参考

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

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