[leetcode] Largest Number


Largest Number

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

For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.

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

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

 

 

A wrong approach.  It’s plausible, but too messy. And it causes runtime error, I don’t figure out why so far.

//Can input be empty?
//Can input contains illegal elements such as '002'?
struct {
    bool operator()(int a, int b){
            string sa = to_string(a);
            string sb = to_string(b);
            //This is to gurantee that sa is shorter than or equal to sb
            //if(sa.size() > sb.size()){
            //    string tmp = sa;
            //    sa = sb;
            //    sb = tmp;
            //}
            //BUG I can't swap sa and sb since it will mess up the result
            size_t i = 0;
            for(i = 0; i < sa.size() && i < sb.size(); i++){
                if(sa[i] < sb[i]){
                    return false;
                }
                else if(sa[i] > sb[i]){
                    return true;
                }
            }
            //sb is longer than sa
            while(i < sb.size()){
                if(sa[sa.size() - 1] < sb[i]){
                    return false;
                }
                else if(sa[sa.size() - 1] > sb[i]){
                    return true;
                }
                else{
                    i++;
                }
            }
            //sa is longer than sb
            while(i < sa.size()){
                if(sb[sb.size() - 1] < sa[i]){
                    return true;
                }
                else if(sb[sb.size() - 1] > sa[i]){
                    return false;
                }
                else{
                    i++;
                }
            }
            //sb is at the same length of sa or the longer part of sb contains the same digit to the last digit of sa
            return true;//Or false, both are OK
    }
} myLess;

class Solution {
public:
    string largestNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end(), myLess);
        string ans;
        for(auto it = nums.begin(); it != nums.end(); it++){
            ans = ans.append(to_string(*it));
        }
        
        //delete heading 0s
        if(ans[0] == '0') ans = "0";
        return ans;
    }
};

 

Instead, write a compare function, if (to_string[a] + to_string[b] > to_string[b] + to_string[a]) we consider that a should be placed prior to b.

class Solution {
public:
    string largestNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end(), [](int a, int b){
            string sa = to_string(a);
            string sb = to_string(b);
            string ans1 = sa.append(sb);
            string ans2 = sb.append(sa);
            for(size_t i = 0; i < ans1.size(); i++){
                if(ans1[i] < ans2[i]){
                    return false;
                }
                else if(ans1[i] > ans2[i]){
                    return true;
                }
            }
            return false;
        });
        string ans;
        for(size_t i = 0; i < nums.size(); i++){
            ans = ans.append(to_string(nums[i]));
        }
        if(ans[0] == '0') ans = "0";
        return ans;
    }
};

Untitled

 

Leave a comment

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.