Leetcode exercise - Sword finger offer 45. arrange the array into the smallest number

1. Title Description

The finger of the sword Offer 45. Make the array the smallest number
Enter an array of nonnegative integers , Put all the numbers in the array together to form a number , Print the smallest of all the numbers that can be spliced .

Example 1:

 Input : [10,2]
 Output : "102"

Example 2:

 Input : [3,30,34,5,9]
 Output : "3033459"

2. Problem solving ideas and codes

2.1 Their thinking

This question is very simple , Make the numbers in the array as small as possible , Then let the smaller the front row be in front , In this way, the higher the number of digits, the smaller the number . Then we can convert numbers into strings for splicing , After being converted into a string, we are actually comparing whether the lexicographic order after the numbers are spliced is the smallest . Based on this idea , First, we convert a number array into a string list , Then sort the string list , The collation compares the dictionary order after the splicing of two strings , Finally, you can splice the string list and return . With 3 and 30 For example , First, splice the two numbers , There are two splicing methods , The results are 330 and 303

Then compare the dictionary order of two numbers , Because the dictionary order starts from left to right , Just meet the meaning of the topic , So let's compare the first place of the two numbers , The first one is 3 So the next one compares , here 0 The dictionary order of is less than 3 , therefore 303 Than 330 smaller , return 303.

2.2 Code

class Solution {
    
    public String minNumber(int[] nums) {
    
        StringBuilder builder = new StringBuilder();
        List<String> list = new ArrayList<>();
        for (int num : nums) {
    
            list.add(String.valueOf(num));
        }
        list.sort((o1, o2) -> {
    
            String s1 = o1 + o2;
            String s2 = o2 + o1;
            return s1.compareTo(s2);
        });
        for (String s : list) {
    
            builder.append(s);
        }
        return builder.toString();
    }
}

2.3 test result

Pass the test

3. summary

• Convert a number array into a string list for processing
• Sort the list in dictionary order , Finally, return the list splicing results