(python版)《剑指Offer》JZ32：把数组排成最小的数

本文主要是介绍(python版)《剑指Offer》JZ32：把数组排成最小的数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

牛客
Leetcode
在这里插入图片描述
本质上是一个排序问题

【思路1】快速排序

排序判断规则： 设 nums 任意两数字的字符串格式 a 和 b ，则

若ab > ba 则 a “大于” b，<b在前 a在后>
若ab < ba 则 a “小于” b，<a在前 b在后>
若ab = ba 则 a “等于” b.

在这里插入图片描述
快排代码参考


class Solution:def minNumber(self, nums: List[int]) -> str:def fast_sort(l , r):if l >= r: returni, j = l, rwhile i < j:while strs[j] + strs[l] >= strs[l] + strs[j] and i < j: j -= 1while strs[i] + strs[l] <= strs[l] + strs[i] and i < j: i += 1strs[i], strs[j] = strs[j], strs[i]strs[i], strs[l] = strs[l], strs[i]fast_sort(l, i - 1)fast_sort(i + 1, r)strs = [str(num) for num in nums]fast_sort(0, len(strs) - 1)return ''.join(strs)
'''
作者：jyd
链接：https://leetcode-cn.com/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/
来源：力扣（LeetCode）
'''

在这里插入图片描述

In [1]: nums = [3,30,34,5,9]                                                                                                                                      In [16]:In [2]: strs = [str(num) for num in nums]In [3]: strs
Out[3]: ['3', '30', '34', '5', '9']

【思路2】py内置函数 sort，cmp_to_key

class Solution:def minNumber(self, nums: List[int]) -> str:def sort_rule(x, y):a, b = x + y, y + xif a > b: return 1elif a < b: return -1else: return 0strs = [str(num) for num in nums]strs.sort(key = functools.cmp_to_key(sort_rule))return ''.join(strs)
'''
作者：jyd
链接：https://leetcode-cn.com/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/
来源：力扣（LeetCode）
'''
'''

sort方法的key参数 需要设置一个函数，这个函数返回元素参与大小比较的值
在这里插入图片描述
cmp_to_key函数的机制还是不太了解

它接受两个参数，对它们进行比较，并返回 一个负数表示小于，零表示相等，或者一个正数表示大于。
键函数是一个可调用的函数，它接受一个参数并返回另一个值作为 排序键 使用。

=============================
3 和 30比较， -1是指要交换
34 和 3、30比较，返回1，表示34比他们大，都不交换
5为什么跟3、34比较呢？

比较的是前两个就好了么？
那为什么先跟3比较，而不是34？5比34大的话，就是比3大了呀。

9为什么也只跟前两个比？跟5比较，大的话，直接放后面了呀，怎么先跟34比？

==============================
以上是我的疑问，哪位路过的大佬可以赐教一二？

在这里插入图片描述

【附】思路1的打印版

class Solution:def minNumber(self, nums):def fast_sort(l , r):print('此时l=%d,r=%d'%(l,r))if l >= r: print('提前结束')returni, j = l, rwhile i < j:while strs[j] + strs[l] >= strs[l] + strs[j] and i < j: # print('%s >= %s'%(strs[j] + strs[l],strs[l] + strs[j]))print('%s %s >= %s %s'%(strs[j],strs[l],strs[l],strs[j]),end='\t')j -= 1print('l=%d, 新j=%d'%(l,j))while strs[i] + strs[l] <= strs[l] + strs[i] and i < j: print('%s %s <= %s %s'%(strs[i],strs[l],strs[l],strs[i]),end='\t')i += 1print('l=%d, 新i=%d'%(l,i))strs[i], strs[j] = strs[j], strs[i]print('i j 相遇：交换 %s 和 %s'%(strs[i],strs[j]))print('现在strs = ',strs)strs[i], strs[l] = strs[l], strs[i]print('交换  %s 和 %s'%(strs[i],strs[l]))print('获得排好的j前面序列,现在strs = ',strs)print('\n')fast_sort(l, i - 1)print('左半部分')fast_sort(i + 1, r)print('右半部分')strs = [str(num) for num in nums]print('原strs = ',strs)fast_sort(0, len(strs) - 1)return ''.join(strs)s = Solution()
nums = [3,30,34,5,9]
s.minNumber(nums)

思路2的打印版

class Solution:def minNumber(self, nums):def sort_rule(x, y):a, b = x + y, y + xprint('\na=%s,b=%s'%(a,b))if a > b: print('返回1')return 1elif a < b: print('返回-1')return -1else: print('返回0')return 0strs = [str(num) for num in nums]print('原strs = ',strs)strs.sort(key = functools.cmp_to_key(sort_rule))print('最后的strs = ',strs)return ''.join(strs)s = Solution()
nums = [3,30,34,5,9]
s.minNumber(nums)