|
题目描述：输入一个整型数组，将数组里的所有数字连起来组成一个数字，输出所有可能的数字中最小的一个。
比如现在输入一个数组 {3,32,321}，那么输出的最小的数应该是 321323. -------题目来自 剑指offer.
思路：最直接的方法是列出所有的组合情况，然后找出最小的那个数。但是这样时间复杂度是 n! ，复杂度太大。
另寻思路，我们知道在排序里面最快的排序算法时间复杂度为 nlogn，那么我们可以借助快速排序的思想进行排序，从而时间复杂度只需要 nlogn。但是快速排序比较的是两个数的大小，我们现在需要比较的是哪个数应该放在前面哪个数放在后面。比如 上面例子 321 > 32 > 3，但是顺序却是 321 32 3 这样排。这个时候我们需要自己定义一个比较的函数，来确定哪个数比较“大”应该放在后面，哪个应该比较“小”放在前面。
我们观察到， 32132 > 32321，而 332 > 323 ,所以321在32前面，32 在 3 前面。所以我们不是比较两个数谁比较大，而时应该比较两个数谁放在前面组成的数比较大，思路有了，接下来就是实现了！
先自定义一个比较函数 compare ：利用Integer的特性，将整型数字转换，接着转换为String类型进行比较。
//自定义一个比较函数，如果 a 大于 b 则输出 true 否则输出 false ，大于，不是简单的 a > b ，而是指 两个数字连起来，ab > ba
public static boolean compare(int a,int b){
boolean p = false;
Integer aa = a;
Integer bb = b;
String aStr = aa.toString() + bb.toString();
String bStr = bb.toString() + aa.toString();
if(Integer.valueOf(aStr) >= Integer.valueOf(bStr))
p = true;
return p;
}
接下来就利用快速排序的思想进行排序了！排序后再将得到的数组从头到尾输出！
import java.util.Scanner;
public class printMinNumber {
public static void main(String args[]){
Scanner scan = new Scanner(System.in);
while(scan.hasNext()){
int n = scan.nextInt();
int[] arr = new int[n];
for(int i = 0; i < n; i++){
arr[i] = scan.nextInt();
}
printMinNumber(arr,n);
}
}
public static void printMinNumber(int[] arr,int n){
qSort(arr,n,0,n - 1);
for(int ele : arr)
System.out.print(ele);
}
//快速排序，将数组元素按照从小到到排序
public static void qSort(int[] arr,int n,int left,int right){
if(left < right){
int index = Partition(arr,n,left,right);
qSort(arr,n,left,index - 1);
qSort(arr,n,index + 1,right);
}
}
//利用快速排序思想进行排序
public static int Partition(int[] arr,int n,int left,int right){
int temp = arr[left];
while(left < right){
while(left < right && !compare(temp,arr[right]))
right--;
if(left < right)
arr[left++] = arr[right];
while(left < right && compare(temp,arr[left]))
left++;
if(left < right)
arr[right--] = arr[left];
}
arr[left] = temp;
return left;
}
//自定义一个比较函数，如果 a 大于 b 则输出 true 否则输出 false ，大于，不是简单的 a > b ，而是指 两个数字连起来，ab > ba
public static boolean compare(int a,int b){
boolean p = false;
Integer aa = a;
Integer bb = b;
String aStr = aa.toString() + bb.toString();
String bStr = bb.toString() + aa.toString();
if(Integer.valueOf(aStr) >= Integer.valueOf(bStr))
p = true;
return p;
}
}
| 
转播
