[LeetCode] 179. Largest Number

Posted on | In

Problem

Given a list of non negative integers, arrange them such that they form the largest number.

Example 1:

1
2
Input: [10,2]
Output: "210"

Example 2:

1
2
Input: [3,30,34,5,9]
Output: "9534330"

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

Explanation

  1. If we find out the most significatn digit by using c = n / Math.pow(10, log10(n)), then it’s complicated.

  2. We can convert each integer number to string, then make a comparator to compare two string’s concatnation and sort them.

  3. Special case is if the first string starts with 0 like 00, we can return 0 as the result.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public String largestNumber(int[] nums) {
        if (nums == null || nums.length == 0) return "0";

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

        Arrays.sort(arr, (String a, String b) -> {
            return (b+a).compareTo(a+b);
        });

        StringBuilder sb = new StringBuilder();
        for (String s: arr) {
            sb.append(s);
        }
        if (sb.charAt(0) == '0') {
            return "0";
        } else {
            return sb.toString();
        }
    }
}