题解 | #最大数#

class Solution {
public:
    /**
     * 最大数
     * @param nums int整型vector 
     * @return string字符串
     */
    string solve(vector<int>& nums) {
        // write code here
        nums = quikSort(nums);
        if(nums[0] == 0){
            return "0";
        }
        return numsToString(nums);
    }
    
    //比较排列先后
    bool comSolve(int a,int b){
        int left = a;
        int right = b;
        if(a >= 1000){
            right = b * 10000 + a;
        }else if(a >= 100){
            right = b * 1000 + a;
        }else if(a >= 10){
            right = b * 100 + a;
        }else{
            right = b * 10 + a;
        }
        
        if(b >= 1000){
            left = a * 10000 + b;
        }else if(b >= 100){
            left = a * 1000 + b;
        }else if(b >= 10){
            left = a * 100 + b;
        }else{
            left = a * 10 + b;
        }
        
        return left >= right;
    }
    
    //排序
    vector<int> quikSort(vector<int> & nums){
        if(nums.size() <= 1){
            return nums;
        }
        vector<int> left;
        vector<int> right;
        for(int i=1;i<nums.size();i++){
            if(comSolve(nums[i],nums[0])){
                left.push_back(nums[i]);
            }else{
                right.push_back(nums[i]);
            }
        }
        left = quikSort(left);
        right = quikSort(right);
        left.push_back(nums[0]);
        left.insert(left.end(),right.begin(),right.end());
        return left;
    }
    
    //转字符串
    string numsToString(vector<int> & nums){
        string res = "";
        for(int i=0;i<nums.size();i++){
            res += to_string(nums[i]);
        }
        return res;
    }
};

class Solution {
public:
    /**
     * 最大数
     * @param nums int整型vector 
     * @return string字符串
     */
    string solve(vector<int>& nums) {
        // write code here
        quikSort(nums,0,nums.size()-1);
        if(nums[0] == 0){
            return "0";
        }
        return numsToString(nums);
    }
    
    //比较排列先后
    bool comSolve(int a,int b){
        return to_string(a)+to_string(b) <= to_string(b)+to_string(a);
    }
    
    //排序
    void quikSort(vector<int> & nums,int left,int right){
        if(left >= right){
            return;
        }
        
        int i=left,j = right;
        int base = nums[left];
        while(i<j){
            while(comSolve(nums[j],base) && i < j) {
                j--;
            };
            while(comSolve(base,nums[i]) && i < j) {
                i++;
            };;
            
            if(i<j){
                swap(nums[i], nums[j]);
            }
        }
        
        nums[left] = nums[i];
        nums[i] = base;
        
        quikSort(nums, left, i-1);
        quikSort(nums, i+1, right);
    }
    
    //转字符串
    string numsToString(vector<int> & nums){
        string res = "";
        for(int i=0;i<nums.size();i++){
            res += to_string(nums[i]);
        }
        return res;
    }
};