例如輸入數(shù)組{3, 32, 321},則掃描輸出這 3 個數(shù)字能排成的最小數(shù)字 321323。
先求出這個數(shù)組中所有數(shù)字的全排列,然后把每個排列拼起來,最后求出拼起來的數(shù)字的最大值。
找到一個排序規(guī)則,數(shù)組根據(jù)這個規(guī)則排序之后能排成一個最小的數(shù)字。要確定排序規(guī)則,就要比較兩個數(shù)字,也就是給出兩個數(shù)字 m 和 n,我們需要確定一個規(guī)則判斷 m 和 n 哪個應該排在前面,而不是僅僅比較這兩個數(shù)字的值哪個更大。
根據(jù)題目的要求,兩個數(shù)字 m 和 n 能拼接成數(shù)字 m 和 m。如果 mn < nm,那么我們應該打印出 m,也就是 m 應該排在 n 的前面,我們定義此時 m 小于 n:反之,如果 nm < mn,我們定義 n 小于 m。如果 mn=nm,m 等于 n。在下文中,符號“<”、“>”及“=”表示常規(guī)意義的數(shù)值的大小關系,而文字“大于”、“小于”、“等于”表示我們新定義的大小關系。
接下來考慮怎么去拼接數(shù)字,即給出數(shù)字 m 和 n,怎么得到數(shù)字 m 和 m 并比較它們的大小。直接用數(shù)值去計算不難辦到,但需要考慮到一個潛在的問題就是 m 和n 都在 int 能表達的范圍內,但把它們拼起來的數(shù)字 m 和 m 用 int 表示就有可能溢出了,所以這還是一個隱形的大數(shù)問題。
一個非常直觀的解決大數(shù)問題的方法就是把數(shù)字轉換成字符串。另外,由于把數(shù)字 m 和 n 拼接起來得到 m 和 m,它們的位數(shù)肯定是相同的,因此比較它們的大小只需要按照字符串大小的比較規(guī)則就可以了。
本題采用第二種方法實現(xiàn)。
public class Test33 {
/**
* 自定義的排序比較器,實現(xiàn)算法說明的排序原理
*/
private static class MComparator implements Comparator<String> {
@Override
public int compare(String o1, String o2) {
if (o1 == null || o2 == null) {
throw new IllegalArgumentException("Arg should not be null");
}
String s1 = o1 + o2;
String s2 = o2 + o1;
return s1.compareTo(s2);
}
}
/**
* 快速排序算法
*
* @param array 待排序數(shù)組
* @param start 要排序的起始位置
* @param end 要排序的結束位置
* @param comparator 自定義的比較器
*/
private static void quickSort(String[] array, int start, int end, Comparator<String> comparator) {
if (start < end) {
String pivot = array[start];
int left = start;
int right = end;
while (start < end) {
while (start < end && comparator.compare(array[end], pivot) >= 0) {
end--;
}
array[start] = array[end];
while (start < end && comparator.compare(array[start], pivot) <= 0) {
start++;
}
array[end] = array[start];
}
array[start] = pivot;
quickSort(array, left, start - 1, comparator);
quickSort(array, start + 1, end, comparator);
}
}
/**
* 題目:輸入一個正整數(shù)數(shù)組,把數(shù)組里所有數(shù)字拼接起來排成一個數(shù),
* 打印能拼接出的所有數(shù)字中最小的一個。
* @param array 輸入的數(shù)組
* @return 輸出結果
*/
public static String printMinNumber(String[] array) {
if (array == null || array.length < 1) {
throw new IllegalArgumentException("Array must contain value");
}
MComparator comparator = new MComparator();
quickSort(array, 0, array.length - 1, comparator);
StringBuilder builder = new StringBuilder(256);
for (String s : array) {
builder.append(s);
}
return builder.toString();
}
public static void main(String[] args) {
String[] data = {"3", "5", "1", "4", "2"};
System.out.println(printMinNumber(data));
String[] data2 = {"3", "32", "321"};
System.out.println(printMinNumber(data2));
String[] data3 = {"3", "323", "32123"};
System.out.println(printMinNumber(data3));
String[] data4 = {"1", "11", "111"};
System.out.println(printMinNumber(data4));
String[] data5 = {"321"};
System.out.println(printMinNumber(data5));
}
}
http://wiki.jikexueyuan.com/project/for-offer/images/47.png" alt="" />