LeetCode 179 Largest Number
Given a list of non negative integers, arrange them such that they form the largest number.
For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.
Note: The result may be very large, so you need to return a string instead of an integer.
就一道题做了我一下午。。。临时又想不起来quick sort实现时的细节了。。。第n次练习，希望能够再次加深认识。。。
大致思路是自己写一个compare函数，重新定义两个数的大小关系，排序完后直接concatenate数组即可获得最大number对应的string。
那如何compare呢？
对于两个数str1，str2，我们是要比较str1+str2与str2+str1的大小：
比如123，321，我们要比较123321与321123的大小。
按照上述逻辑实现即可。
有一个tricky的地方是，如果所有数为0，那么最后得到的str会是000...000一串0，因此需要单独判断这个情况。
代码：
public class Solution {
public String largestNumber(int[] nums) {
// Implement a variety of quick sort
String str = "";
int len = nums.length;
if (len == 0) return str;
// Sort the array in increasing order, so reversely concatenate the array is the result string
quickSort(nums, 0, len - 1);
if (nums[len-1] == 0) return new String("0");
for (int num: nums) {
String n = num + "";
str = n + str;
}
return str;
}
public void quickSort(int[] nums, int l, int r) {
int pindex = partition(nums, l, r);
if (l < pindex-1) quickSort(nums, l, pindex - 1);
if (pindex < r) quickSort(nums, pindex, r);
}
public int partition(int[] nums, int l, int r) {
int i = l, j = r;
int pivot = nums[l + (r-l)/2];
while (i <= j) {
while (compare(nums[i], pivot) == -1) i++;
while (compare(nums[j], pivot) == 1) j--;
if (i <= j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
i++;
j--;
}
}
return i;
}
public int compare(int num1, int num2) {
String str1 = "" + num1;
String str2 = "" + num2;
String s1 = str1 + str2, s2 = str2 + str1;
for (int i = 0, j = 0; i < s1.length() && j < s2.length(); i++, j++) {
if (s1.charAt(i) > s2.charAt(j)) return 1;
else if (s1.charAt(i) < s2.charAt(j)) return -1;
}
return 0;
}
}
看了一下discuss，其实没必要自己实现quicksort，只需重写一个comparator函数，调用Arrays.sort(nums, cmp)即可。。。心塞。。。
代码如下：
public class Solution {
public String largestNumber(int[] num) {
if(num == null || num.length == 0) return "";
// Convert int array to String array, so we can sort later on
String[] s_num = new String[num.length];
for(int i = 0; i < num.length; i++)
s_num[i] = String.valueOf(num[i]);
// Comparator to decide which string should come first in concatenation
Comparator<String> comp = new Comparator<String>(){
@Override
public int compare(String str1, String str2){
String s1 = str1 + str2;
String s2 = str2 + str1;
return s2.compareTo(s1); // reverse order here, so we can do append() later
}
};
Arrays.sort(s_num, comp);
// An extreme edge case by lc, say you have only a bunch of 0 in your int array
if(s_num[0].charAt(0) == '0') return "0";
StringBuilder sb = new StringBuilder();
for(String s: s_num)
sb.append(s); return sb.toString();
}
}
