题目
输入一个正整数数组,把数组里面的所有属猪拼接起来成为一个数打印能拼接起来的所有数字中最大/最小的那个。
思考
直观想法就是求出这个数组中所有数字的全排列,然后拼接起来,再比较大小即可,当然复杂度过高。
另一个想法,我们可以定义一个排序规则,如下:
如果两个数m,n能拼接成数字mn,nm,如果mn>nm,则m应该在n前面,反之亦然
根据这个排序规则,我们可以重新排列数组,将排列好的数组拼接起来输出即可'为了方便比较,并且防止数据溢出(比如C语言),采用字符串的方式拼接。我们很容易可以写出如下代码:
1
2
3
4
5
6
7
8
9
|
def compare(strNum1, strNum2): newStrNum1 = strNum1 + strNum2 newStrNum2 = strNum2 + strNum1 if newStrNum2 > newStrNum1: return - 1 elif newStrNum2 = = newStrNum1: return 0 else : return 1 |
问题
排序规则定义好了,但是问题来了,一般的 sorted 排序函数 都有相应的 cmp函数,用来定制化排序的比较方法。但是python3的sorted函数已经删去了cmp参数,真不能跑去用python2吧
解决方案
由于python3中sorted函数除去compare函数,无法自定义排序规则,所以使用内置的函数,将cmp函数转化为key的值
Note:
functools.cmp_to_key() 将 cmp函数 转化为 key。
cmp函数的返回值 必须为 [1,-1,0]
python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
from functools import cmp_to_key def compare(strNum1, strNum2): """ 返回最小排列的定义,如果需要最大,将返回值的+1、-1调换即可 """ newStrNum1 = strNum1 + strNum2 newStrNum2 = strNum2 + strNum1 if newStrNum2 > newStrNum1: return - 1 elif newStrNum2 = = newStrNum1: return 0 else : return 1 def print_min_nums(nums): if not nums: return 0 arr = [ str (i) for i in nums] newarr = sorted (arr,key = cmp_to_key(compare)) return "".join(newarr) if __name__ = = '__main__' : print (print_min_nums([ 3 , 32 , 321 ])) |
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持服务器之家。
原文链接:https://www.cnblogs.com/r1-12king/p/13201769.html