个人解法
本题采用自定义比较+快速排序的方法解决
主要是自定义比较,这里分为n中可能
-
3和3这种 无疑相等,谁在前谁在后是一样的
-
4和321这种,首字符不相等的情况下,首字符小的要在前面,组成3214,而不是4321
-
3和321这种,首字符相等的情况下,str1先遍历完了,接着将str2接下来的字符与str1的首字符进行比较,依然是小的在前面。最后比较后拼接的结果是3213,而不是3321。同理,如果321在前面,也是这样比较。
代码有点多,没去优化,将就看了哈哈。
public class Solution {
public int compare(String str1, String str2){
int index=0, len1=str1.length(),len2=str2.length();
while(index<len1 && index<len2){
char c1=str1.charAt(index),c2=str2.charAt(index);
if(c1==c2)
index++;
else if(c1>c2)
return 1;
else
return -1;
}
//str1先遍历完,str2还没遍历完
char c1_start = str1.charAt(0);
while(index<len2){
if(str2.charAt(index)==c1_start)
index++;
else if(str2.charAt(index)<c1_start)
return 1;
else
return -1;
}
//str2先遍历完,str1还没遍历完
char c2_start = str2.charAt(0);
while(index<len1){
if(str1.charAt(index)==c2_start)
index++;
else if(str1.charAt(index)>c2_start)
return 1;
else
return -1;
}
return 0;
}
//快速排序
public void qSort(String[] str,int l,int r){
//递归终止条件
if(l>=r)
return;
int left=l, right=r;
String pivot = str[left];
while(left<right){
//从右边往左扫描,找到比pivot小的字符串
while(compare(str[right],pivot)>=0 && left<right) right--;
if(left<right)
str[left] = str[right];
//从左边往右扫描,找到比pivot大的字符串
while(compare(str[left],pivot)<=0 && left<right) left++;
if(left<right)
str[right] = str[left];
if(left<=right)
str[left] = pivot;
}
//分别对左右子序列进行快速排序
qSort(str,l,right-1);
qSort(str,right+1,r);
}
public String PrintMinNumber(int [] numbers) {
int len = numbers.length;
//转成字符串数组
String[] res = new String[len];
for(int i=0;i<len;++i){
res[i] = String.valueOf(numbers[i]);
}
//方法一 暴力解法排序 O(n*2)
for(int i=0;i<len-1;++i){
for(int j=i+1;j<len;++j){
if(compare(res[i],res[j])>0){
String temp = res[i];
res[i] = res[j];
res[j] = temp;
}
}
}
//方法二 快速排序 O(nlogn)
qSort(res,0,len-1);
String ans = "";
for(String s:res){
ans += s;
}
return ans;
}
}