剑指 Offer 45. 把数组排成最小的数

题目

传送门

解题思路

这题属实让eclipse坑了一把，不说那话。这题我一开始想的复杂了，最开始想用的HashMap进行求解，将最高位按照低到高进行排列，每个最高位内部再进行一次排列，这样最后就直接按顺序将所有的整数以字符串的形式拼接并输出就可以，但是还是太年轻了，如果只考虑最高位的话，会出现多个最高位相同的情况例如：334,35,369等等，这样的话就会导致一个问题，即多个相同值的key（最高位都一样）都会指向唯一一个value，这样最后每一种最高位都只剩下一个数，显然不合要求；第二次考虑使用二维数组进行实现，同样遇到了不可弥补的问题。最后，还是采用了题解中的一种做法，就是相邻两个数进行正反拼接，若nums[j]+nums[j+1]>nums[j+1]+nums[j],注意这里的加法是字符串的加法，不是数字相加，nums[j]应移动到j+1的后面去，这里的排序就是用冒泡（毕竟要求用冒泡），排序完成后再按照顺序进行字符串拼接，最后进行输出。其实这里涉及到一个问题，也就是排序规则的传递性问题，意思是，每次比较都是相邻两个数拼接之后比较，排序完成后怎样保证字符串 满足xy < yx , yz < zy 时 xz < zx 一定成立。后面给出K神关于传递性的证明。

传递性证明

设十进制数 x, y, z 分别有 a, b, c 位，则有：
（左边是字符串拼接，右边是十进制数计算，两者等价）
xy = x * 10^b + y 
yx = y * 10^a + x

则 xy < yx 可转化为：
x * 10^b + y < y * 10^a + x
x (10^b - 1) < y (10^a - 1)
x / (10^a - 1) < y / (10^b - 1)     ①

同理， 可将 yz < zy 转化为：
y / (10^b - 1) < z / (10^c - 1)     ②

将 ① ② 合并，整理得：
x / (10^a - 1) < y / (10^b - 1) < z / (10^c - 1)
x / (10^a - 1) < z / (10^c - 1)
x (10^c - 1) < z (10^a - 1)
x * 10^c + z < z * 10^a + x
∴  可推出 xz < zx ，传递性证毕

代码

class Solution {
    public String minNumber(int[] nums) {
               String[] str=new String[nums.length];
       for(int i=0;i<nums.length;i++) {
    	   str[i]=nums[i]+"";
       }
       boolean swapped=true;
       for(int i=0;i<str.length-1;i++) {
    	   if(!swapped) {
    		   break;
    	   }
    	   swapped=false;
    	   for(int j=0;j<str.length-1-i;j++) {
    		   if((str[j]+str[j+1]).compareTo(str[j+1]+str[j])>=0) {
                     String tmp="";
		             tmp=str[j];
		             str[j]=str[j+1];
		             str[j+1]=tmp;
    			   swapped=true;
    		   }
    	   }
       }

       String res="";
       for(String v:str) {
    	   res+=v;
       }
       return res;
    }
}

知识点

比较两个String字符串类型数据大小

方法一

如果两个数String字符串中只包含数字0~9和小数点

String a = "32";
String b = "334";

// 首先将两个数都转换为int 数据
int a_N = Integer.valueOf(a);
int b_N = Integer.valueOf(b);
// 比较大小
boolean res = a_N > b_N;

方法二

如果两个String字符串中包含字母，则使用a.compareTo(b)函数
该方法是用于判断一个字符串时大于、等于还是小于另一个字符串。判断字符串大小的一句是根据他们在字典中的顺序决定的。

语法：str1.compareTo(str2);

该函数的返回值为int类型
若str1等于参数字符串str2，则返回0；
若str1大于参数字符串str2，则返回值大于0；
若str1小于参数字符串str2，则返回值小于0；
Java中的compareTo()方法，返回参与比较的前后两个字符串的ASCII码的差值

String a = "3";
String b = "32a";
int res = a.compareTo(b); // 如果 a > b 则返回res > 0; 
						// 如果 a < b 则返回res < 0; 

数组的长度

nums.length;