剑指offer45 把数组排成最小的数
文章目录
- 剑指offer45 把数组排成最小的数
- 题目描述
- 思路
- 实现
- 参考文献
题目描述
输入一个非负整数数组,把数组里的所有数字拼接起来排成一个数,打印能拼接出来的所有数字中最小的一个。
思路
此题求拼接起来的最小数字,本质上是一个排序问题。设数组nums中任意两数字的字符串为x和y, 则规定排序判断规则为:
- 若拼接字符串x+y > y+x, 则x“大于”y, 排在右边。
- 反之,若x+y < y+x, 则x"小于”y. 排在左边。
根据以上规则,套用任何排序方法对nums执行排序即可。
算法流程
1.初始化:字符串列表strs, 保存各数字的字符串格式。
2.列表排序:应用以上“排序判断规则”,对strs执行排序。
3.返回值:拼接strs中的所有字符串,并返回。
实现
可以使用自己实现快速排序,也可以调用C++的内置函数sort.
sort(strs.begin(), strs.end(),[](string& x, string& y){return x+y<y+x})
这里使用了c++的Lambda表达式语法。Lambda表达式的各个部分如下图:
对应的解释如下:
- capture 子句(在 C++ 规范中也称为 Lambda 引导。)
- 参数列表(可选)。 (也称为 Lambda 声明符)
- mutable 规范(可选)。
- exception-specification(可选)。
- trailing-return-type(可选)。
- Lambda 体。
在上述sort函数调用的过程中,仅使用到了空的capture 子句,参数列表和lambda体。
参考文献
[1] https://leetcode.cn/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/solution/mian-shi-ti-45-ba-shu-zu-pai-cheng-zui-xiao-de-s-4/
[2] c++ lambda表达式 https://learn.microsoft.com/zh-cn/cpp/cpp/lambda-expressions-in-cpp?view=msvc-170#parts-of-a-lambda-expression
本文链接:https://my.lmcjl.com/post/2477.html
展开阅读全文
4 评论