lintcode379. 将数组重新排序以构造最小值

小咪咪 2023-07-06 14:30 8阅读 0赞

给定一个整数数组，请将其重新排序，以构造最小值。

样例
    样例 1：
    
    输入：[2, 1]
    输出：[1, 2]
    解释：通过将数组重新排序，可构造 2 个可能性数字：
               1+2=12
               2+1=21
    其中，最小值为 12，所以，将数组重新排序后，该数组变为 [1, 2]。
    样例 2：
    
    输入：[3, 32, 321]
    输出：[321, 32, 3]
    解释：通过将数组重新排序，可构造 6 个可能性数字：
    	3+32+321=332321
    	3+321+32=332132
    	32+3+321=323321
    	32+321+3=323213
    	321+3+32=321332
    	321+32+3=321323
    其中，最小值为 321323，所以，将数组重新排序后，该数组变为 [321, 32, 3]。
    挑战
    在原数组上完成，不使用额外空间。
    
    注意事项
    The result may be very large, so you need to return a string instead of an integer.

class Solution {
        
    public:
        /**
         * @param nums: n non-negative integer array
         * @return: A string
         */
        static bool cmp(const int &a,const int &b)
        {
        
            return to_string(a)+to_string(b)<to_string(b)+to_string(a);
        }
        string minNumber(vector<int> &nums) {
        
            // write your code here
            if(nums.size()<=0) return "";
            sort(nums.begin(),nums.end(),cmp);
            string res="";
            for (int i = 0; i < nums.size(); i++) {
        
                /* code */
                res+=to_string(nums[i]);
            }
            if(res[0]=='0')
            {
        
                int i=0;
                while(res[i]=='0'&&i<res.size())i++;
                if(i==res.size()) return "0";
                else return res.substr(i);
            }
            return res;
        }
    };