引言
最近，有位大神同学在到处面试，在群里抛出了一些面试题，于是有了这篇文章，对排序算法的一次复习。
问题
大神同学遇到的问题，来源于179. Largest Number，本人还是习惯英文版（刷题在两年前。。。）。
Given a list of non negative integers, arrange them such that they form the largest number. Example 1: Input: [10,2] Output: "210"
解题思路
- 可以把这个问题看成是一个排序问题，毕竟是通过不同的数字排列来获取最优解的， 那么谁在前，谁在后呢？
210 > 102 2 * 10^2 + 10 > 10 * 10 + 2
- 可以得出，
与
的比较，前者大，则
a排在前面，后者大则b排在前面。
排序算法的选择
快速排序的变形
- 时间复杂度平均为
，当然最坏情况是
，与测试用例强相关。
class Solution {
public String largestNumber(int[] nums) {
quickSort(nums, 0, nums.length - 1);
StringBuilder max = new StringBuilder();
for (int num : nums) {
// 特殊情况的处理
if (nums[0] == 0) {
return "0";
} else {
max.append(num);
}
}
return max.toString();
}
private static void quickSort(int[] nums, int low, int high) {
if (low < high) {
int index = getIndex(nums, low, high);
if (index == -1) {
return;
}
quickSort(nums, low, index - 1);
quickSort(nums, index + 1, high);
}
}
private static int getIndex(int[] nums, int low, int high) {
int flag = nums[low];
boolean isZero = true;
while (low < high) {
while (low < high && compareNum(flag, nums[high]) >= 0) {
if (nums[high] != 0) {
isZero = false;
}
high --;
}
nums[low] = nums[high];
while (low < high && compareNum(nums[low], flag) >= 0) {
if (nums[low] != 0) {
isZero = false;
}
low++;
}
nums[high] = nums[low];
}
nums[low] = flag;
// 全是0 只扫描一次
if (isZero) {
return -1;
}
return low;
}
}
Arrays.sort排序，使用TimSort，时间复杂度最好情况为，平均情况为
，实现方式为自定义
Comparator。
class Solution {
public String largestNumber(int[] nums) {
List<Integer> list = new ArrayList<>();
for (int num : nums) {
list.add(num);
}
// TimSort
list.sort(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return compareNum(o1, o2);
}
});
StringBuilder max = new StringBuilder();
for (int num : list) {
if (list.get(0) == 0) {
return "0";
} else {
max.append(num);
}
}
return max.toString();
}
private static int compareNum(int a, int b) {
String str1 = String.valueOf(a);
String str2 = String.valueOf(b);
int len1 = str1.length();
int len2 = str2.length();
double sum1 = Math.pow(10, len2) * a + b;
double sum2 = Math.pow(10, len1) * b + a;
if (sum2 > sum1) {
return 1;
} else if (sum1 > sum2) {
return -1;
} else {
return 0;
}
}
}
结语
说明算法实在不是笔者的强项，而且TimSort原理也在学习中。
