0179 Largest Number

Problem Description

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

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

Example 1

Input: nums = [10,2]
Output: "210"

Example 2

Input: nums = [3,30,34,5,9]
Output: "9534330"

Solution

Clearly, we need to make sure the most significant digit has the largest digit. Sorting the list of numbers would be a natural idea, while the only problem appears when two numbers have different number of digits and the common part are the same, for example 34 and 341. Naive comparing gives 341 > 34, but in fact we want 34 > 341 since 34341 > 34134. Thus we need to change the definition of compare operator, or define a new kind of operator. This operator take two strings as input s1, s2 and return s1 > s2 when s1.s2 > s2.s1.

When defining the operator, we have to make sure it respects the transtivity property. That is, if we have s1 > s2 and s2 > s3, we should have s1 > s3. This guarantees that the order of s1 precedes s2 holds no matter when and how many other strings comes, which makes our operator consistent. We can prove this using contradiction method. (Credits goes to iomonad).

Proof

We use a.b to represent the concatenation of non-negative integers a and b .

Theorem:

Let a, b, and c be non-negative integers. If a.b > b.a and b.c > c.b , we have a.c > c.a .

Proof:

We use [a] to denote the length of the decimal representation of a . For example, if a = 10 , we have [a] = 2 .

Since a.b > b.a and b.c > c.b , we have

a 10^[b] + b > b 10^[a] + a
b 10^[c] + c > c 10^[b] + b

, which is equivalent to

a (10^[b] - 1) > b (10^[a] - 1)
b (10^[c] - 1) > c (10^[b] - 1)

Obviously, 10^[a] - 1 > 0 , 10^[b] - 1 > 0 , and 10^[c] - 1 > 0 . Since c >= 0 , according to the above inequalities, we know that b > 0 and a > 0 . After multiplying the above two inequalities and cancelling b and (10^[b] - 1) , we have

a (10^[c] - 1) > c (10^[a] - 1)

This is equivalent to

a 10^[c] + c > c 10^[a] + a

, which means a.c > c.a .

Q.E.D.

C++ Code

class Solution {
private:
static bool comp(string& i,string& j) { 
    return (i+j > j+i);
}

public:
    string largestNumber(vector<int>& nums) { // basically define a new compare operation
        int n = nums.size();
        vector<string> helper(n);
        for(int i=0;i<n;i++) helper[i] = to_string(nums[i]);
        sort(helper.begin(), helper.end(), comp);
        
        if(helper[0][0] == '0') return "0";
        string ret="";
        for(auto s:helper){
            ret += s;
        }
        return ret;
    }
};
文章目录