##題目描述 輸入一個正整數陣列，把陣列里所有數字拼接起來排成一個數，列印能拼接出的所有數字中最小的一個，例如輸入陣列{3，32，321}，則列印出這三個數字能排成的最小數字為321323，
思路
Collections.sort()排序，
時間復雜度O(nlgn)，空間復雜度O(n)，
compareTo代碼
import java.util.ArrayList;
import java.util.Collections;
public class Solution {
public String PrintMinNumber(int [] numbers) {
ArrayList<String> arrayList = new ArrayList<String>();
for(int i : numbers){
arrayList.add( i + "" );
}
Collections.sort(arrayList, (s1,s2)->(s1+s2).compareTo(s2+s1));
StringBuilder stringBuilder2 = new StringBuilder();
for(String s : arrayList){
stringBuilder2.append(s);
}
return stringBuilder2.toString();
}
}
手寫compare代碼
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
public class Solution {
public String PrintMinNumber(int [] numbers) {
ArrayList<String> arrayList = new ArrayList<String>();
for(int i : numbers){
arrayList.add( i + "" );
}
Collections.sort(arrayList, new Comparator<String>() {
public int compare(String s1, String s2) {
int i = 0, j = 0;
while(i < s1.length() || j < s2.length()) {
if(i == s1.length()) i = 0;
if(j == s2.length()) j = 0;
if(s1.charAt(i) < s2.charAt(j)) return -1;
if(s1.charAt(i) > s2.charAt(j)) return 1;
i++; j++;
}
return 0;
}
});
StringBuilder stringBuilder2 = new StringBuilder();
for(String s : arrayList){
stringBuilder2.append(s);
}
return stringBuilder2.toString();
}
}
筆記
手寫compare比直接構造兩個字串進行compareTo在時間空間復雜度上都有所區別，
- 手寫compare運行時間記憶體大致為：34ms 9748k
- 用compareTo運行時間記憶體大致為：233ms 16016k
在compareTo前構造了兩個拼接字串，這是多余的消耗，
根據String類的compareTo原始碼，在函式內部又將兩個String轉成了字符陣列，又是多余的消耗，
而這些消耗都可以通過自己手寫compare規則避免，整個演算法主要在于sort，而sort又主要在于compare，
compareTo原始碼：
public int compareTo(String anotherString) {
int len1 = value.length;
int len2 = anotherString.value.length;
int lim = Math.min(len1, len2);
char v1[] = value;
char v2[] = anotherString.value;
int k = 0;
while (k < lim) {
char c1 = v1[k];
char c2 = v2[k];
if (c1 != c2) {
return c1 - c2;
}
k++;
}
return len1 - len2;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/83467.html
標籤：其他
上一篇：整數中1出現的次數
下一篇：丑數