Share my c++ solutions


  • 0
    Q

    thought:

    1. convert number in array to string
    2. sort with specific comp function compare(const string&a, const string& b). swap a, b when:
      a. if a[i] > b[i] && i++ < min(a.length(), b.length())
      b. (a+b)>(b+a)
    3. output string by go through string array with descending order

    Here is the code:

    class Solution {
    public:
        string largestNumber(vector<int> &num) {
            vector<string> str_num;
            int num_len = num.size();
            string ret;
            if (num_len == 0)
                return ret;
            
            int i;
            for( i = 0; i < num_len; i++)
            {
                str_num.push_back(to_string(num[i]));
            }
            
            std::stable_sort(str_num.begin(), str_num.end(), compare);
            for(i = num_len-1; i>= 0; i--)
            {
                ret += str_num[i];
            }
            
            //if first character is 0, string should be "0"
            if (ret[0] == '0')
                ret = "0";
            
            return ret;
        }
        
        static bool compare(const string& a, const string& b)
        {
            int a_len = a.length();
            int b_len = b.length();
            int i,j;
            i=j=0;
            
            while ((i < a_len) && (j < b_len) && (a[i] == b[j]) )
            {
                i++;
                j++;
            }
            
            if ((i == a_len) && (j == b_len))
                return true;
            
            if (i == a_len || j == b_len)
            {
                string tmp1 = a+b;
                string tmp2 = b+a;
                return (tmp1.compare(tmp2)<0);
            }
            
            return (a[i]<b[j]);
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.