Reorder array to construct the minimum number

小鱼儿 2022-07-17 00:15 66阅读 0赞

**Reorder array to construct the minimum number**

题目

> Construct minimum number by reordering a given non-negative integer  
> array. Arrange them such that they form the minimum number.
> 
> Notice
> 
> The result may be very large, so you need to return a string instead  
> of an integer.

--------------------

> Example Given \[3, 32, 321\], there are 6 possible numbers can be  
> constructed by reordering the array:
> 
> 3+32+321=332321  
> 3+321+32=332132  
> 32+3+321=323321  
> 32+321+3=323213  
> 321+3+32=321332  
> 321+32+3=321323  
> So after reordering, the minimum  
> number is 321323, and return it.

--------------------

lintcode[题目链接][Link 1]

1.O(n)log(n)时间复杂度

算法很简单，就是需要细心。

--------------------

class Solution {
    public:
        /**
         * @param nums n non-negative integer array
         * @return a string
         */
        string intToStr(int num){
            stringstream ss;
            ss<<num;
            string str;
            ss>>str;
            ss.clear();
            return str;
        }
        static bool cmp(const string &a,const string &b){
       //自定义排序函数
            int i;
            if(a.size()==b.size())
                return a<b;
            else
            {
                for(i=0;i<min(b.size(),a.size());i++)//关键部分
                {
                    if(a[i]<b[i])
                        return true;
                    if(a[i]>b[i])
                        return false;
                }
                //这里是考虑　32 和　321　等的特殊情况
                if(b.size()==i)
                {
                    if(a[i]>b[i-1])
                        return false;
                    return true;
                }
                if(a.size()==i)
                {
                    if(b[i]>a[i-1])
                        return true;
                    return false;
                }
            }
        }
        string minNumber(vector<int>& nums) {
            // Write your code here
            vector<string> str_nums(nums.size());
            string ans,str;
            int i;
            for(i=0;i<nums.size();i++)
                str_nums[i]=intToStr(nums[i]);
            sort(str_nums.begin(),str_nums.end(),cmp);
            for(i=0;i<str_nums.size();i++)
                str+=str_nums[i];
            //这里需要排除输出时前面有０的情况
            for(i=0;i<str.size();i++)
            {
                if(str[i]!='0')
                    break;
            }
            for(int k=i;k<str.size();k++)
                ans+=str[k];
            if(ans.empty())   ans="0";
            return ans;
        }
    };

--------------------

[Link 1]: http://www.lintcode.com/en/problem/reorder-array-to-construct-the-minimum-number/