[题解]剑指 Offer 45. 把数组排成最小的数(C++)
2021/8/26 20:06:29
本文主要是介绍[题解]剑指 Offer 45. 把数组排成最小的数(C++),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目
输入一个非负整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。
示例 1:
输入: [10,2] 输出: "102"
示例 2:
输入: [3,30,34,5,9] 输出: "3033459"
提示:
- 0 < nums.length <= 100
说明:
- 输出结果可能非常大,所以你需要返回一个字符串而不是整数
- 拼接起来的数字可能会有前导 0,最后结果不需要去掉前导 0
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
核心思想就是排序,对于x和y,哪个数放在前面使得拼接后的数更小就把哪个数放在前面。如果会C++标准库函数的sort(),很容易就搞定了。排序之后从头到尾拼接即可。如果想了解sort()函数的用法,可以看这里:https://en.cppreference.com/w/cpp/algorithm/sort
时间复杂度O(n*log(n)),空间复杂度O(log(n))。
代码
class Solution { public: string minNumber(vector<int>& nums) { sort(nums.begin(), nums.end(), [&](const int a, const int b){ return to_string(a) + to_string(b) < to_string(b) + to_string(a); }); string ans = ""; for(const int& x : nums) { ans += to_string(x); } return ans; } };
这篇关于[题解]剑指 Offer 45. 把数组排成最小的数(C++)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-05feign默认connecttimeout和readtimeout是多少-icode9专业技术文章分享
- 2024-07-05idea控制台,日志太多,导致部分想看得日志被刷走 搜不到-icode9专业技术文章分享
- 2024-07-05The server selected protocol version Tls10 is not accepted by client preferences [TLs12]-icode9专业技术文章分享
- 2024-07-05怎么清理项目缓存-icode9专业技术文章分享
- 2024-07-04安装 Eyoucms详细图文教程-icode9专业技术文章分享
- 2024-07-04ueditor 复制文章时,图片的链接是一个下载图片地址,该如何处理?-icode9专业技术文章分享
- 2024-07-04怎样判断host有没有对wordpress有缓存呢-icode9专业技术文章分享
- 2024-07-04具有编译功能的系统make后,无法ssh连接-icode9专业技术文章分享
- 2024-07-04make后如何升级ssh-icode9专业技术文章分享
- 2024-07-03微信支付提示下单账户与支付账户不一致-icode9专业技术文章分享