剑指offer——把数组排成最小的数

1 题目描述

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

2 题目分析

利用排序，改写比较器进行排序。
Java中的Collections类

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
public class Solution {public String PrintMinNumber(int [] numbers) {int len=numbers.length;ArrayList<Integer> list=new ArrayList<Integer>();//String s=null;String s="";if(numbers==null || len==0){return s;}for(int i=0;i<len;i++){list.add(numbers[i]);}Collections.sort(list,new Comparator<Integer>(){@Overridepublic int compare(Integer s1,Integer s2){//思考：为什么要把Integer变为String进行比较？？见下分析String str1=s1+""+s2;String str2=s2+""+s1;/*注意：字符串大小比较不能用大于号、小于号以及等于号if(str1>str2){return 1;}else if(str1<str2){return -1;}else(str1==str2){return 0;}*///字符串大小比较用compareTo函数return str1.compareTo(str2);}});/*利用foreachfor(int k:list){s=s+k;}*///传统for循环实现遍历for(int k=0;k<list.size();k++){s=s+list.get(k);}return s;}
}

思考：为什么要把Integer变为String进行比较？
因为题目要求要用拼接比较大小，若直接用Integer进行比较，则比较的是两个数相加的和，若简单拼接进行比较，必须进行字符串的拼接。

知识点：使用 String.compareTo 方法：

compareTo() 的返回值是int, 它是先比较对应字符的大小(ASCII码顺序)

1. 如果字符串相等返回值0
2. 如果第一个字符和参数的第一个字符不等,结束比较,返回他们之间的差值（ascii码值）（负值前字符串的值小于后字符串，正值前字符串大于后字符串）
3. 如果第一个字符和参数的第一个字符相等,则以第二个字符和参数的第二个字符做比较,以此类推,直至比较的字符或被比较的字符有一方全比较完,这时就比较字符的长度.

3 其它写法

利用StringBuilder。

import java.util.ArrayList;
//import java.util.Collections;
import java.util.Arrays;
import java.util.Comparator;
public class Solution {public String PrintMinNumber(int [] numbers) {int len=numbers.length;if(numbers==null || len==0){return "";}String[] str=new String[len];StringBuilder sb=new StringBuilder();for(int i=0;i<len;i++){str[i]=String.valueOf(numbers[i]);//注意此处，int型转换为String型的方法！！！}/*Collections.sort(str,new Comparator<String>(){@Overridepublic int compare(String s1,String s2){String c1=s1+s2;String c2=s2+s1;return c1.compareTo(c2);}});*///思考：这里不能用Collections.sort是因为什么？？？Arrays.sort(str,new Comparator<String>(){@Overridepublic int compare(String s1, String s2) {String c1 = s1 + s2;String c2 = s2 + s1;return c1.compareTo(c2);}});for(int j=0;j<len;j++){sb.append(str[j]);}return sb.toString();//注意此处，StringBuilder转换为String型的方法！！！}
}

这个解题方法思考：这里不能用Collections.sort是因为什么？？？

参考学习：

1. Java中的Collections类
2. Java——对字符的操作：Character，String，StringBuffer，StringBuilder