179 Largest Number

179. Largest Number

1. Question

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.

2. Implementation

(1) Sort

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

        int n = nums.length;
        String[] strs = new String[n];

        for (int i = 0; i < n; i++) {
            strs[i] = nums[i] + "";
        }

        Arrays.sort(strs, (a, b)->((b + a).compareTo(a + b)));

        if (strs[0].charAt(0) == '0') {
            return "0";
        }

        StringBuilder res = new StringBuilder();
        for (String str : strs) {
            res.append(str);
        }
        return res.toString();
    }
}

3. Time & Space Complexity

时间复杂度O(nlogn), n是nums里的元素个数, 空间复杂度O(n)