剑指offer:把数组排成最小的数
2024-10-20 15:47:43
题目描述:
输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字为321323。
思路分析:
正常的思路是用一个全排列,那么复杂度为O(n!)。
这里实际要考察的是一个排序的方式。试想对于每两个数,例如3,32,可以拼成332和323,那么显然此时在这个问题当中32排在3前面更好。因此就实现一个比较函数,实现这个比较。同时注意需要将整数转换为字符串后可以直接拼接,这里用的是头文件<string>当中的to_string函数。具体的实现看代码。
代码:
class Solution {
public:
string PrintMinNumber(vector<int> numbers) {
int len = numbers.size();
if(len<=)
return "";
sort(numbers.begin(), numbers.end(), cmp);
string res;
for(int i=; i<len; i++)
res += to_string(numbers[i]);
return res;
}
private:
static bool cmp(int a, int b)
{
string A = to_string(a)+to_string(b);
string B = to_string(b)+to_string(a);
return A<B;
}
};
最新文章
- shader forge卡通渲染!
- XE7 提交 App(iOS 8)提示「does not contain the correct beta entitlement」问题修复
- codeforces 712C C. Memory and De-Evolution(贪心)
- ASP.NET C# 日期 时间 年 月 日 时 分 秒 格式及转换(转自happymagic的专栏)
- 强调语气<;strong>;和<;em>;标签,文字设置单独样式<;span>;
- 133. Clone Graph 138. Copy List with Random Pointer 拷贝图和链表
- Linux Deepin 2014安装Lenovo LJ2600D驱动
- C++Primer学习笔记
- Eclipse生成Jar包方法
- android最近心得整理
- JS基础与循环
- (11.13)Java小知识!
- JUC中AQS简介
- Java记事本编写第一个程序“你好,世界”
- Flask表单(form)的应用
- python之组合与重用性
- armeabi和armeabi-v7a(转)
- iOS runtime实用篇--和常见崩溃say good-bye!
- 到网上收集了一个“高大上”的CSS3登入表单和大家分享一下
- Android Service总结01 目录