《剑指offer》---把数组排成最小的数

本文算法使用python3实现

1 题目描述：

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组 $ [3，32，321] $ ，则打印出这三个数字能排成的最小数字为 $ 321323 $ 。

时间限制：1s；空间限制：32768K

2 思路描述：

大致思路：

（1）我们可以先思考只有两个数字的情况： $ [3,32] $ ，可以看出来 $ 332 > 323 $ 因此需要把数组改变为 $ [32,3] $ ；

（2）对于有三个数字的情况： $ [3,32,321] $ 我们两两进行比较， $ 332 > 323 $ 于是，将 $ 3 $ 与 $ 32 $ 交换位置变成 $ [32,3,321] $ 而 $ 3321 > 3213 $ 于是将 $ 3 $ 与 $ 321 $ 继续交换位置到 $ [32,321,3] $ ；接着我们继续使用 $ 32 $ 进行比较，由于 $ 32321 > 32132 $ 将 $ 32 与 321 $ 进行位置交换为 $ [321,32,3] $ 此时，将数组链接起来变成 $ 321323 $ 即为最小的数。

具体思路：

（1）先将数字列表转化成字符串链表，这样便于在一个字符串后面直接加上另外一个字符串。也就是 $ "3" + "321" = "3321" $ 。

（2）构造一个比较函数，当 $ str1 + str2 > str2 + str1 $ 时我们认为字符串 $ str1 > str2 $ 。

（3）将字符串列表按照比较函数的规定进行冒泡排序（或其它方法排序），将定义为”大”的字符串放到最后。而”小”的字符串放在前面。最后将字符串列表链接起来，便是所求。

注意：在python2.x中可直接对 sort() 函数进行比较函数cmp的传参，可以利用sort()函数直接对字符串列表进行排序。但是，对于python3.x取消了sort()函数中的cmp参数。

3 程序代码：

（1）方法一：

class Solution:

	def theMax(self, str1, str2):

		'''定义字符串比较函数'''

		return str1 if str1+str2 > str2+str1 else str2

	def PrintMinNumber(self, numbers):

		"""使用冒泡进行排序(把最大的放最后)"""

		string = [str(num) for num in numbers]

		res = []

		flag = True

		count = len(string) - 1

		while flag and  count > 0:

			flag = False

			for i in range(len(string)-1):

				if self.theMax(string[i], string[i+1]) == string[i]:

					temp = string[i]

					del string[i]

					string.insert(i+1, temp)

					flag = True

			count -= 1

		string = ''.join(string)

		return string

（3）方法二（仅python2.x可用）：

class Solution:

	def cmp(self, a, b):

		'''定义比较函数'''

		ab = int(a+b)

		ba = int(b+a)

		return 1 if ab > ba else -1

	def PrintMinNumber(self, numbers):

		string = [str(num) for num in numbers]

		string.sort(self.cmp, reverse=True)

		return ''.join(string)

巴特西

《剑指offer》---把数组排成最小的数

1 题目描述：

2 思路描述：

3 程序代码：

最新文章

热门文章