Largest Number——STL的深层理解

Given a list of non negative integers, arrange them such that they form the largest number.

For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.

Note: The result may be very large, so you need to return a string instead of an integer.

分析，刚开始的时候想着用基数排序来做，看到网上的分析，直接应用STL中的排序函数，只要重新定义一个符合特殊要求的比较函数就行了，顿时觉得简单多了·····················

转自：http://www.cnblogs.com/ganganloveu/p/4228832.html

首先考虑两个数字拼在一起会有越界的可能性，所以，要用字符串来存储。（这个特别重要，许多的题都需要这样来做）

这次关键在于排序compare，也就是怎样比较a和b的拼接顺序。

这样来考虑：

如果完全相同，那么返回false。

如果在相同位数下已经比较出结果，比如12 vs. 131，由于2<3，因此13112比12131来的大，返回true。

如果在相同位数下无法判断，比如12 vs. 1213。记相同部分为s1，后续部分为s2，就变成比较s1s2s1和s1s1s2的大小关系，转化为比较s1与s2的大小关系。

由于12<13，因此12<1213，应为121312而不是121213，返回true。

排完序只要逆序加就可以了（大的在前面），注意全0时简写为一个0.

注意函数atoi的使用和c_str以及to_string的使用，这些都是我不太熟悉的地方。

class Solution {

public:

    static bool compare(int a, int b)

    {

        string as = to_string(a);

        string bs = to_string(b);

        int sizea = as.size();

        int sizeb = bs.size();

        int i = ;

        while(i<sizea && i<sizeb)

        {

            if(as[i] < bs[i])

                return true;

            else if(as[i] > bs[i])

                return false;

            i ++;

        }

        if(i==sizea && i==sizeb)

            return false;   //equal returns false

        else if(i==sizea)

        {//as finished

            if(bs[i] == '')

                return false;

            else

                return compare(atoi(as.c_str()), atoi(bs.substr(i).c_str()));

        }

        else

        {//bs finished

            if(as[i] == '')

                return true;

            else

                return compare(atoi(as.substr(i).c_str()), atoi(bs.c_str()));

        }

    }

    string largestNumber(vector<int> &num) {

        sort(num.begin(), num.end(), compare);

        int size = num.size();

        string ret;

        while(size--)

            ret += to_string(num[size]);

        if(ret[] != '')

            return ret;

        else

            return "";

    }

};

巴特西

Largest Number——STL的深层理解

最新文章

热门文章