把数组排成最小的数【Java版】
把数组排成最小的数
http://www.nowcoder.com/practice/8fecd3f8ba334add803bf2a06af1b993
方法1:base on 冒泡排序
import java.util.ArrayList; public class Solution { public String PrintMinNumber(int [] numbers) { String res = ""; for(int i = 0; i<=numbers.length-2; ++i){//排成最小数字==>字典序最小 //【贪心算法思想:局部最优到全局最优】 for(int j=0; j<=numbers.length-2-i; ++j){ String s1 = "" + numbers[j] +numbers[j+1]; String s2 = "" + numbers[j+1] +numbers[j]; if(s1.compareTo(s2)>0){//对于String之间的比较,使用str1.compareTo(str2) 若str1>str2则返回正。 int temp = numbers[j]; numbers[j] = numbers[j+1]; numbers[j+1] = temp; } } } for(int i=0; i<=numbers.length-1; ++i){ res += numbers[i]; } return res; } } //时间O(N^2)
关于String和int类型的强制转换:
long x1=Integer.valueOf(""+numbers[j]+numbers[j+1]);//中间的位置有个""空字符串,不然int直接相加了 long x2=Integer.valueOf(String.valueOf(numbers[j+1])+String.valueOf(numbers[j]));//两种写法,本行是稳妥规范版 // 相互转化: // String->int,使用Integer.valueOf(); // int->String使用String.valueOf()
方法2:base on 快排
import java.util.ArrayList; public class Solution { public String PrintMinNumber(int [] numbers) { String res =""; Partition(0, numbers.length-1, numbers); for(int i=0; i<=numbers.length-1; ++i){ res += numbers[i]; } return res; } public void Partition(int left, int right, int [] numbers){ if(left < right){ int l = left; int r = right; int temp = numbers[left]; while(left < right){ while(left < right && ((""+ temp + numbers[right]).compareTo(""+ numbers[right] + temp)<=0)) --right;//快排永远的等号 numbers[left] = numbers[right]; while(left < right && (("" + temp + numbers[left]).compareTo("" + numbers[left] + temp))>=0) ++left; numbers[right] = numbers[left]; } numbers[left] = temp; int divide = left; Partition(l, divide-1, numbers); Partition(divide+1, r, numbers); } } }//时间O(NlogN) //空间O(logN)==>快排,栈深度是logN,每层空间O(1)
《剑指Offer-Java题解》 文章被收录于专栏
《剑指Offer-Java题解》