[sword finger offer] 45 Arrange the array into the smallest number

The finger of the sword Offer 45. Make the array the smallest number

subject

Enter an array of nonnegative integers , Put all the numbers in the array together to form a number , Print the smallest of all the numbers that can be spliced .

Ideas

  String sorting problem , Set array nums The string of any two numbers in is x and y, The sorting rule is ：

• x + y > y + x, be x Greater than y
• x + y < y + x, be x Less than y

Then convert the list of numbers to an array of strings , Use quick sort to sort an array of strings ,（ The main purpose of sorting is to make the high-order numbers as small as possible , Big numbers are placed in the lower order ）, Finally, the strings in the string array are spliced into a numeric string .

Code

class Solution {
    
public:
    string minNumber(vector<int>& nums) {
    
        vector<string> strs;
        //  Convert a number to a string and save 
        for(int i = 0; i < nums.size(); i++)
        {
    
            strs.push_back(to_string(nums[i]));
        }
        //  Quick sort  
        quickSort(strs,0,strs.size() - 1);
        //  Put the smallest combination   Put in string 
        string res;
        for(string s:strs)
        {
    
            res.append(s);
        }
        return res;
    }

private:
    void quickSort(vector<string>& strs,int l,int r)
    {
    
        if(l >= r)
        {
    
            return;
        }
        int i = l,j = r;
        while(i < j)
        {
    
            //  Compare string sizes   find jl < lj stop it  
            //  Why and l  because l Is the largest digit of a number ！
            while(strs[j] + strs[l] >= strs[l] + strs[j] && i < j)
            {
    
                j--;
            }
            
            // il > li  stop it   Find the one with a large value   Put it back 
            while(strs[i] + strs[l] <= strs[l] + strs[i] && i < j)
            {
    
                i++;
            }
            //  In exchange for   Make the high-order number smaller   The lower digit becomes larger   Overall smaller 
            swap(strs[i],strs[j]);
        }

        swap(strs[i],strs[l]);
        quickSort(strs,l,i - 1);
        quickSort(strs,i + 1, r);

    }

};