【题目】

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.

【分析】

数字转换为字符串，按字典序从大到小排序，并拼接在一起就是最大的数

【代码】

/*********************************
*   日期：2015-01-18
*   作者：SJF0115
*   题目: 179.Largest Number
*   网址：https://oj.leetcode.com/problems/largest-number/
*   结果：AC
*   来源：LeetCode
*   时间复杂度：O(n)
*   空间复杂度：O(n)
*   博客：
**********************************/
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        using namespace std; class Solution { public: static bool cmp(const string &a,const string &b){ string ab = a + b; string ba = b + a; return ab > ba; } string largestNumber(vector
       
         &num) { int count = num.size(); vector
        
          vec; if(count == 0){ return NULL; }//if // 整数转换为字符串 int zeroCount = 0; for(int i = 0;i < count;++i){ // 统计0的个数 if(num[i] == 0){ zeroCount ++; }//if char str[20]; sprintf(str,"%d",num[i]); vec.push_back(str); }//for // 处理一个特殊情况 全是0的情况 if(zeroCount == count){ return "0"; }//if // 剪枝 只有一条数据 if(count == 1){ return vec[0]; }//if // 从大到小排序 sort(vec.begin(),vec.end(),cmp); // 拼接一个最大的数 string result; for(int i = 0;i < count;++i){ result += vec[i]; }//for return result; } }; int main(){ Solution solution; vector
         
           num; num.push_back(3); num.push_back(30); num.push_back(34); num.push_back(5); num.push_back(9); // 重新排列 string result = solution.largestNumber(num); // 输出 cout<
          
           
 
           
           
 
           
 
           
特别注意一个特殊情况：
 
           

 
 
           
全是0的情况，只返回一个0即可。