- 转载请注明作者和出处:http://blog.csdn.net/u011475210
- 代码地址:https://github.com/WordZzzz/Note/tree/master/AtOffer
- 刷题平台:https://www.nowcoder.com/
- 题 库:剑指offer
- 编 者:WordZzzz
题目描述
输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字为321323。
解题思路
遇到这个题,全排列当然可以做,但是时间复杂度为O(n!)。在这里我们自己定义一个规则,对拼接后的字符串进行比较。
排序规则如下:
- 若ab > ba 则 a 大于 b,
- 若ab < ba 则 a 小于 b,
- 若ab = ba 则 a 等于 b;
根据上述规则,我们需要先将数字转换成字符串再进行比较,因为需要串起来进行比较。比较完之后,按顺序输出即可。
C++版代码实现
1 | class Solution { |
Python版代码实现
1 | # -*- coding:utf-8 -*- |
系列教程持续发布中,欢迎订阅、关注、收藏、评论、点赞哦~~( ̄▽ ̄~)~
完的汪(∪。∪)。。。zzz