“This is the 9th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

1, the title

Given a set of non-negative integer nums, rearrange the order of each number (each number is not separable) to form the largest integer.

Note:

  • The output can be quite large, so you need to return a string instead of an integer.

Example 1:

Input: nums = [10,2]Copy the code

Example 2:

Nums = [3,30,34,5,9] output: "9534330"Copy the code

Example 3:

Input: nums = [1]Copy the code

Example 4:

Nums = [10] Output: "10"Copy the code

2, train of thought

(Greedy)O(nlogn)O(nlogn) O(nlogn)O(nlogn)

Given a set of non-negative numbers, rearrange them to form the largest integer.

Sample:

As shown in the example, the largest number [3,30,34,5,9] can make up is “9534330”.

Given our array of two numbers [a,b], if the combination of “ab” is greater than the combination of “ba”, then we choose a to concatenate preferentially. For example, nums = [10,2], the combination of “210” is obviously greater than the combination of “102”, so we choose 2 for concatenation first, and then we define a collation rule.

However, when it comes to a sequence, in order for a sequence to be able to correctly customize its sorting, such sorting rules need to meet the full ordering relation, that is, the following three relations:

  • ifA, b or less 且 B or less 则 a = b(Antisymmetry)
  • ifA, b or less 且 B, c or less 则 A c or less(Transitivity)
  • ifA, b or less 或 B or less(Completeness)

Detailed proof can be read. If the full order relationship is satisfied, we can reorder the NUMS array according to the custom sorting rules, and finally return the concatenated string.

Implementation details:

C++ custom sort, implement a CMP function.

static bool cmp(int a,int b) // Custom collation rules
    {
        string as = to_string(a), bs = to_string(b);
        return as + bs > bs + as;
    }
Copy the code

Java custom sort, arrays.sort () with lamda expressions.

Arrays.sort(s, (a, b) -> {
            String x = a + b, y = b + a ;
            return y.compareTo(x);
 });  
Copy the code

The specific process is as follows:

  • 1, custom collation function, willnumsThe array is resorted according to custom collation rules.
  • 2. Traverse from start to finishnumsArray, fetchnumsConcatenate each number in the answer stringresIn the.
  • 3. Judge the stringresWhether all0If it is all0, the return"0"Otherwise returnres.

Time complexity analysis: The time complexity of sorting is O(nlogn)O(nLogn)O(nlogn).

C++ code

class Solution {
public:
    static bool cmp(int a,int b) // Custom collation rules
    {
        string as = to_string(a), bs = to_string(b);
        return as + bs > bs + as;
    }
    string largestNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end(), cmp);
        string res;
        for(auto x : nums) res += to_string(x);
        if(res[0] = ='0') return "0"; // Check if all zeros are present
        returnres; }};Copy the code

4. Java code

class Solution {
    public String largestNumber(int[] nums) {
        int n = nums.length;
        String[] s = new String[n];
        for (int i = 0; i < n; i++) s[i] = nums[i] + "";
        Arrays.sort(s, (a, b) -> {  // Custom collation rules
            String x = a + b, y = b + a ;
            return y.compareTo(x);
        });    
        StringBuilder res = new StringBuilder();
        for (String x : s) res.append(x);
    	if(res.charAt(0) = ='0') return "0"; // Check if all zeros are present
        returnres.toString(); }}Copy the code

179. Maximum number