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 is9534330.

Note: The result may be very large, so you need to return a string instead of an integer.

Analysis:

Merge Sort or Quick Sort, but sorting logic is based on comparing 2 Strings

59 > 592

59 > 58

59 > 48

59 < 5960

...

basically, always check char from left to right(high to low)

1. if 2 string with same length, which ever show up with a higher value char, is greater
2. if 2 string with diff length:
   1. if SAME according to "1", take the shorter string compare with longer string's substring and see what happens.

Complexity:

Time: O(nlogn)

Space: O(n) - helper

Code:

public class Solution {
    public String largestNumber(int[] nums) {
        if(nums == null || nums.length == 0){
            return "";
        }
        String[] strs = new String[nums.length];
        for(int i = 0; i < nums.length; i++){
            strs[i] = Integer.toString(nums[i]);
        }

        ms(strs, 0, strs.length-1);

        StringBuilder sb = new StringBuilder();

        for(String str : strs){
            sb.append(str);
        }

        if(sb.charAt(0)=='0')
        {
            return "0";
        }
        return sb.toString();
    }

    private void ms(String[] strs, int s, int e){
        if(s >= e){
            return;
        }
        int m = s + (e-s)/2;
        ms(strs, s, m);
        ms(strs, m+1, e);
        merge(strs, s, e, m);
    }

    private void merge(String[] strs, int s, int e, int m){
        String[] helper = new String[strs.length];
        for(int i = s; i <= e; i++){
            helper[i] = strs[i];
        }

        int i = s, j = m+1, current = s;
        while(i <= m && j <= e){
            if(greater(helper[i], helper[j])){
                strs[current++] = helper[i++];
            }
            else{
                strs[current++] = helper[j++];
            }
        }

        for(int k = i; k <= m; k++){
            strs[current++] = helper[k];
        }
    }

    private boolean greater(String a, String b){
        int index = 0;
        while(index < a.length() && index < b.length()){
            if(a.charAt(index) > b.charAt(index)){
                return true;
            }
            else if(a.charAt(index) < b.charAt(index)){
                return false;
            }
            index++;
        }
        if(a.length() == b.length()){
            return true;
        }

        if(index >= a.length()){
            return greater(a, b.substring(index));
        }
        else
        {
            return greater(a.substring(index), b);
        }
    }
}