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.

就一道題做了我一下午。。。臨時(shí)又想不起來(lái)quick sort實(shí)現(xiàn)時(shí)的細(xì)節(jié)了。。。第n次練習(xí)，希望能夠再次加深認(rèn)識(shí)。。。

大致思路是自己寫一個(gè)compare函數(shù)，重新定義兩個(gè)數(shù)的大小關(guān)系，排序完后直接concatenate數(shù)組即可獲得最大number對(duì)應(yīng)的string。

那如何compare呢？
對(duì)于兩個(gè)數(shù)str1，str2，我們是要比較str1+str2與str2+str1的大?。?br> 比如123，321，我們要比較123321與321123的大小。
按照上述邏輯實(shí)現(xiàn)即可。

有一個(gè)tricky的地方是，如果所有數(shù)為0，那么最后得到的str會(huì)是000...000一串0，因此需要單獨(dú)判斷這個(gè)情況。

代碼：

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，其實(shí)沒(méi)必要自己實(shí)現(xiàn)quicksort，只需重寫一個(gè)comparator函數(shù)，調(diào)用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();           
  }
}