[LeetCode]179.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 is9534330.

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 <iostream>
#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <vector>
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<int> &num) {
        int count = num.size();
        vector<string> 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<int> 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<<result<<endl;
    return 0;
}

特别注意一个特殊情况：

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