AcWing 58 把数组排成最小的数
发布日期:2021-05-28 16:30:46 浏览次数:17 分类:技术文章

本文共 713 字,大约阅读时间需要 2 分钟。

题目描述:

输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。

例如输入数组[3, 32, 321],则打印出这3个数字能排成的最小数字321323。

样例

输入:[3, 32, 321]输出:321323

注意:输出数字的格式为字符串

分析:

分析一下样例,3,32,321,最高位相同,则比较次位,次位为空,比如3,则可将次位都视为3,所以排序后相当于321,323,333这样的有序序列。但是实际操作并不需要这样,对于a和b拼接的数,我们通过比较字符串ab和ba大小就可以确定哪个在前整个数最小。比如32132 < 32321,所以可以自定义这样的cmp函数对原数组排序后再输出即可。

注意:cmp函数前面之所以用static修饰是因为,这是交互式问题,在类的内部调用,不声明为静态的话,在调用cmp时只能通过this指针来调用了。

class Solution {public:    static bool cmp(int a,int b){        string x = to_string(a),y = to_string(b);        return x + y < y + x;    }    string printMinNumber(vector
& nums) { sort(nums.begin(),nums.end(),cmp); string s = ""; for(auto x : nums) s += to_string(x); return s; }};

 

转载地址:https://blog.csdn.net/qq_30277239/article/details/88382379 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:AcWing 59 把数字翻译成字符串
下一篇:AcWing 57 数字序列中某一位的数字

发表评论

最新留言

路过按个爪印,很不错,赞一个!
[***.219.124.196]2024年01月31日 03时44分33秒