/ Data Structure and Algorithms  

Leetcode 179: Largest Number

Question



Given an array, arrange the numbers arbitrarily to form a number with the largest value.

Solution

Intuitively, we should choose the number with largest highest number first. For numbers that start with 9, choose 9 first, then choose numbers that start with 8, then choose ones that start with 7 … and so on.

For example, for 5, 914, 67, choose 914 first, then 67, and then 5, to form 914675. We try to select the number with largest highest number each time to ensure the final number be the biggest.

The next question is what if the highest digit is the same?

  1. If two numbers are equal in length, such as 34 and 30, then obviously, choose the larger one.
  2. If two numbers are not equal in length, such as 3 and 30, then choose 3 or 30 first?

We only need to contac them together and then compare. That is, compare 330 and 303, it is obviously 330 big, so we choose 3 first.

If we think about it, we can find that all we need to do is sort the array by our rules and contac it afterwards.

For the comparision rule, all we have to do is compare the combined number and determine which one should comes first.

For example, for 93, 234, we will compare 93234 and 23493. Then we will choose 93.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public String largestNumber(int[] nums) {
    Integer[] temp = new Integer[nums.length];
 
    // have a copy of nums in Integer
    for (int i = 0; i < nums.length; i++) {
        temp[i] = nums[i];
    }

    // sort the array
    // the compare n1, n2, we compare lexicographic of n1n2 and n2n1
    Arrays.sort(temp, (o1, o2) -> {
        String s1 = o1 + "" + o2;
        String s2 = o2 + "" + o1;

        return s2.compareTo(s1);
    });

    // join the result
    String result =  Arrays.stream(temp).map(Object::toString).collect(Collectors.joining());

    return result.startsWith("0") ? "0" : result;
}