Why is it correct to determine “the relative relation of a concatenated result in a sequence” based on “the lexicographical size”

This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

This is 179 on LeetCode. Maximum number, medium difficulty.

Tag: “Greedy.”

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 very 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

Tip:

• 1 <= nums.length <= 100
• 0 <= nums[i] <=
  $109$

---

Greedy method

For any two values aaa and BBB in numsnumsnums, we cannot directly determine the size/sequence relationship from a conventional perspective.

But we can determine the ordering relationship between AAA and BBB based on the “results” :

If the concatenation results in ababab being better than Bababa, we would expect AAA to come before BBB.

Also, note that we need to deal with leading zeros (save at most one bit).

Code:

class Solution {
    public String largestNumber(int[] nums) {
        int n = nums.length;
        String[] ss = new String[n];
        for (int i = 0; i < n; i++) ss[i] = "" + nums[i];
        Arrays.sort(ss, (a, b) -> {
            String sa = a + b, sb = b + a ;
            return sb.compareTo(sa);
        });
        
        StringBuilder sb = new StringBuilder();
        for (String s : ss) sb.append(s);
        int len = sb.length();
        int k = 0;
        while (k < len - 1 && sb.charAt(k) == '0') k++;
        returnsb.substring(k); }}Copy the code

• Time complexity: Due to being right
  $String$Sort when the sort object is not
  $Java$Fast sorting is not used for basic data types in.Arrays.sort()The underlying implementation of “number of elements/roughly ordered elements” determines whether to use insertion sort or merge sort. It is assumed that “insertion sort” is used. Complexity of
  $O(n^2)$
• Space complexity: O(n)O(n)O(n)

---

prove

For the above solution, we need to prove two things:

• The greedy strategy can get the global optimal solution.
• Such “sort comparison logic” applied to the set numsnumsnums has “full order relation”.

1. The greedy strategy can obtain the global optimal solution

Let the greedy solution obtained by such greedy operation be Ansansans, and the real optimal solution is maxmaxmax.

Since the real optimal solution is the global maximum, and our greedy solution is at least a legal solution (a number), we have ans⩽maxans \leqslant maxans⩽ Max.

Now we just have to prove it
$ans \geqslant max$To have to
$ans = max$(The greedy solution is the optimal solution).

We use “paradox” to prove that ANS ⩾maxans \geqslant maxans⩾ Max is established:

If ANS ⩾maxans \geqslant maxans⩾ Max is not established, that is, ANS

Both ansansans and maxmaxmax are made up of the same number, if ans

This means that we can swap some low and high numbers in Ansansans, making Ansansans larger (adjusted to maxmaxmax), which conflicts with our logic of sorting by “results.”

Therefore, ANS

For example 🌰, if ans

Then in the sorting logic, the whole XXX (maybe not only XXX) should be ranked before the whole YYy (maybe not only YYy).

2. Full order relationship

We use the symbol @@@ to refer to our “sorting” logic:

• If AAA has to come before BBB, we call it a@ba @ba@b;
• If AAA had to come after BBB, we would call it b@ab @ab@a;
• If aaa can be either ahead of BBB or behind BBB, we’ll call it a#ba\#ba#b;

2.1 complete

Completeness means from the set
$nums$Extract any two elements from
$a$ 和
$b$Must satisfy
$a @ b$,
$b @ a$ 和
$a\#b$One of the three.

I don’t really need to prove this, because it’s given by
$a$ 和
$b$Concatenated string
$ab$ 和
$ba$The “lexicographic size relation” is either exactly equal or has an explicit lexicographic size relation, resulting in
$a$Must be at the front or the back.

2.2 Antisymmetry

Antisymmetry is defined by
$a@b$ 和
$b@a$Be able to derive
$a\#b$.

a@ba@ba@b NOTE The lexicographical size of string ababab is larger than that of string bababa.

b@ab@ab@a NOTE The lexicographical size of string ababab is smaller than that of string bababa.

Thus, based on “lexicographical order itself satisfies the full order relation” and “mathematical
$a \geqslant b$ 和
$a \leqslant b$Can be deduced
$a = b$“.

Have to the
$a@b$ 和
$b@a$Be able to derive
$a\#b$.

2.3 transitivity

Transitive means by
$a@b$ 和
$b@c$Be able to derive
$a@c$.

In fact, the “transitivity” here can also be proved by using a similar approach to the official problem solution.

We can use the property that “two concatenated strings of equal length, lexicographical size relation is the same as numeric size relation” to prove this, because strings
$ac$ 和
$ca$It has to be the same length.

Next, let’s start with “custom sorting logic” to prove that a@ca@ca@c:

And then we just have to prove that in different
$i$
$j$Between relationships (there are three cases),
$a@c$Constant establishment can be:

1. When I ==ji ==ji ==j:

2. When I >ji >ji >j:

3. When I

So in summary, we’ve shown that whatever the situation is, if you have
$a@b$ 和
$b@c$If so, then
$a@c$Constant was established.

We can prove transitivity in this way, essentially by using custom sorting logic for determining any element
$a$ 和
$b$The ordering relationship between depends only on
$a$ 和
$b$The relationship between the sizes of the first different elements.

---

Looking for a
$i$The problem of crossing the line

consider

(1) a = 304 b = 30 (2) a = 301 b = 30

Two cases.

Obviously, (1) we get a@ba@ba@b, and (2) we get b@ab@ab@a

But, in this case, III is actually outside the BBB boundary, so can we still look for III? What is b[I]b[I]b[I]?

Actually yes, when we compare AAA and BBB, we are actually comparing ababab and bababa, so we are actually using a[0]a[0]a[0] a[0]a[0]a[0] a[0]a[1]a[1]a[1] A [2]a[2]a[2]… To fill the void left by the end of BBB ontology. In other words, the b in (1) and (2) is actually filled with 303 (fill in a[0]a[0]a[0])

Again for instance

(3) A = 3131248 b = 3131. In comparison, the four digits starting with AAA are actually used to fill the vacancy of BBB, so BBB is actually equivalent to 31313131

---

The last

This is the No.179 of our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 topics in LeetCode by the start date, some of which have locks.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.