Alibi

My Life is Getting Better

Leetcode[179] Largest Number

15 Nov 2015

###Task1 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. ###Python

class Solution(object):
    def largestNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: str
        """
        if not nums or len(nums) == 0:
            return ''
        li = [str(num) for num in nums]
        li.sort(cmp = self.compare)
        return ''.join(li).lstrip('0') or '0'
        
    def compare(self, a, b):
        return [1, -1][ a + b > b + a]

###Java

public class Solution {
    public String largestNumber(int[] nums) {
        if (nums == null || nums.length == 0) {
        	return "";
        }

        String[] arr = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            arr[i] = String.valueOf(nums[i]);
        }

        Arrays.sort(arr, new stringComparator());

        StringBuilder sb = new StringBuilder();
        for (String s: arr) {
            sb.append(s);
        }

        while (sb.charAt(0) == '0' && sb.length() > 1) {
            sb.deleteCharAt(0);
        }
        return sb.toString();
    }
}

class stringComparator implements Comparator<String> {
    public int compare(String s1, String s2) {
        String left = s1 + s2;
        String right = s2 + s1;
        return -left.compareTo(right);
    }
}

###Points

Related Posts