剑指offer32

剑指offer32：把数组排成最小的数

题目描述

题目描述
输入一个正整数数组，把数组里所有数字拼接起来排成一个数，
打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，
则打印出这三个数字能排成的最小数字为321323。

解法一：基于sort排序成最小字符串再拼接

/*
C++ sort() 实现，由于sort()的时间复杂度为O(nlogn)，所以该时间复杂度也为O(nlogn)。
to_string() 可以将int 转化为string,int型不必再转换成string型便可以进行操作了。
要考虑到大数问题（即两个数前后连接之后，可能会溢出），解决方法：通过循环将numbers
数组里的元素赋值到新建的vector<string>容器里，再执行sort()！
*/
class Solution {
public:
    static bool Compare(string num1, string num2)
    {
        string strNum1 = num1;
        strNum1.append(num2);
        string strNum2 = num2;
        strNum2.append(num1);
        return strNum1<strNum2;
    }

    string PrintMinNumber(vector<int> numbers)
    {
        string result = "";
        //判定特殊情况
        if (numbers.size() == 0)
            return result;

        //将数字转换为字符存储
        vector<string> strNum;
        for (int i = 0; i<numbers.size(); i++)
            strNum.push_back(to_string(numbers[i]));

        //排序后strNum已经是最小的字符串了
        sort(strNum.begin(), strNum.end(), Compare);
        for (int i = 0; i<strNum.size(); i++)
            result.append(strNum[i]);
        return result;
    }
};

main函数

#include "stdafx.h"
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    vector<int> numbers = { 3,32,321 };
    Solution a;
    cout<<"最小的组合数字为： "<< a.PrintMinNumber(numbers)<<endl;

    system("pause");
    return 0;
}