剑指offer45 把数组排成最小的数

剑指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表达式的各个部分如下图:

对应的解释如下:

  1. capture 子句(在 C++ 规范中也称为 Lambda 引导。)
  2. 参数列表(可选)。 (也称为 Lambda 声明符)
  3. mutable 规范(可选)。
  4. exception-specification(可选)。
  5. trailing-return-type(可选)。
  6. 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 评论

留下您的评论.