题目描述
输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字为321323。
//一气呵成
选择排序的思想,其实就是比较字符串的大小,将数字小的放在前面,但是比较的是位数,比如说3,23,得到的肯定是233,所以先比较首字符,但是如果一直相同就比较麻烦了,需要将长的那部分与短的首字符比较,这就是helper函数的意义。
1 import java.util.ArrayList;
2
3 public class Solution {
4 public String PrintMinNumber(int [] numbers) {
5 String res="";
6 if(numbers.length==0)
7 return res;
8 String[] arr=new String[numbers.length];
9 for(int i=0;i<numbers.length;i++)
10 arr[i]=""+numbers[i];
11
12 for(int i=0;i<arr.length;i++)
13 {
14 int min=i;
15 for(int j=i;j<arr.length;j++)
16 if(helper(arr[j],arr[min]))
17 min=j;
18 swap(arr,i,min);
19 }
20 for(int i=0;i<arr.length;i++)
21 res+=arr[i];
22 return res;
23
24 }
25 public void swap(String[] arr,int i,int j)
26 {
27 String temp=arr[i];
28 arr[i]=arr[j];
29 arr[j]=temp;
30 }
31 public boolean helper(String s1,String s2)
32 {
33 int len1=s1.length();
34 int len2=s2.length();
35 if(len1>len2)
36 {
37 for(int i=0;i<len1;i++)
38 {
39 if(i<len2)
40 {
41 if(s1.charAt(i)>s2.charAt(i))
42 return false;
43 else if(s1.charAt(i)<s2.charAt(i))
44 return true;
45 }
46 else
47 {
48 if(s1.charAt(i)<s2.charAt(0))
49 return true;
50 else if(s1.charAt(i)>s2.charAt(0))
51 return false;
52 }
53 }
54 return true;
55 }
56 else
57 {
58 for(int i=0;i<len2;i++)
59 {
60 if(i<len1)
61 {
62 if(s1.charAt(i)>s2.charAt(i))
63 return false;
64 else if(s1.charAt(i)<s2.charAt(i))
65 return true;
66 }
67 else
68 {
69 if(s1.charAt(0)<s2.charAt(i))
70 return true;
71 else if(s1.charAt(0)>s2.charAt(i))
72 return false;
73 }
74 }
75 return true;
76 }
77 }
78
79 }