[剑指Offer]45-把数组排成最小的数

题目链接

https://www.nowcoder.com/practice/8fecd3f8ba334add803bf2a06af1b993?tpId=13&tqId=11185&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

题意

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

解题思路

排序,比较器的设计:拼接出的字符串mn<nm则m<n。时间复杂度O(nlogn)。
由于用数字表示mn拼接可能超过int范围,所以使用字符串表示,由于mn nm位数相同,直接使用字符串比较。
由于sort是全局函数,所以cmp要设置成静态函数,这样都不用创建对象即可调。

相关知识

  • 排序函数的比较器要满足:自反性、对称性、传递性 三点。
  • string头文件中的to_string函数可将int型转为string类型。

代码

class Solution {
public:
    string PrintMinNumber(vector<int> numbers) {
        sort(numbers.begin(),numbers.end(),cmp);
        string minNum="";
        if(!numbers.empty()){
            for(auto it=numbers.begin();it!=numbers.end();++it){
                minNum+=to_string(*it);//
            }   
        }
        return minNum;
    }
    static bool cmp(int a,int b){
        string num1="";
        string num2="";
        num1+=to_string(a)+to_string(b);
        num2+=to_string(b)+to_string(a);
        return num1<num2;
    }
};
上一篇:牛客练习赛43 回顾


下一篇:An interesting combinational problem