32.把数组排成最小的数.md

32.把数组排成最小的数

题目描述

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

 

解题思路

下面的思路来自《剑指offer》

• 其实本质上还是排序算法，只不过排序的时候比大小的方式不一样了。将a和b转换成字符串以后，决定哪个应该放到前面的时候无非就两种结果，一种是ab，一种是ba，因此只需要比较ab和ba的大小就能判定a和b的大小。排序的时候使用快速排序就行。

  C++中将数字转换成字符串的函数，std::to_string：

  string to_string (int val);
  string to_string (long val);
  string to_string (long long val);
  string to_string (unsigned val);
  string to_string (unsigned long val);
  string to_string (unsigned long long val);
  string to_string (float val);
  string to_string (double val);
  string to_string (long double val);

 

代码

本来运行的时候报了个错，说sort函数传入的比较函数的返回值必须是静态类型，所以给比较函数的返回值加上static就可以了，后面可以了解一下为什么。

class Solution {
private:
    static bool LessThan(int a, int b){
        string A = to_string(a) + to_string(b);
        string B = to_string(b) + to_string(a);
        return A < B;
    }
public:
    string PrintMinNumber(vector<int> numbers) {
        string result = "";
        int length = numbers.size();
        if(length==0) return result;
        
        sort(numbers.begin(),numbers.end(),LessThan);
        
        for(int i=0; i<length; i++){
            result += to_string(numbers[i]);
        }
        return result;
    }
    
};