[LeetCode] Largest Number 排序

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.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

Hide Tags

Sort

 

---

 

    这题主要的需要考虑排序中的对比判断，对于给定的两个数lft，rgt，误区是直接 lft rgt 判断，根据题目的思路，介意将rgt 接到 lft后面， 与lft 接到 rgt 后面来对比，这样会简单很多，不过这样需要考虑到是否会溢出的问题，题目的验证好像没有对这一问题的严格控制，可以将相接的数值使用 unsigned long int 来存储，这样避免一定情况的溢出。

 

#include <vector>

#include <iostream>

#include <algorithm>

#include <sstream>

using namespace std;

class Solution {

public:

    string largestNumber(vector<int> &num) {

        struct MyCompared

        {

            bool operator ()(int lft,int rgt)

            {

                long unsigned int lidx=,ridx=;

                while(lidx!=)

                    if(lft>=*lidx)  lidx*=;

                    else    break;

                while(ridx!=)

                    if(rgt>=*ridx)  ridx*=;

                    else    break;

                lidx*=;

                ridx*=;

                return lft*ridx+rgt > rgt*lidx+lft;

            }

        }myCompared;

        if(num.size()==)   return "";

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

        ostringstream os;

        if(num[]==)   return "";

        for(int i =;i<num.size();i++)

            os<<num[i];

        return os.str();

    }

};

int main()

{

    vector<int > num{,};

    Solution sol;

    cout<<sol.largestNumber(num)<<endl;

    return ;

}