[剑指-33](php&python):把数组排成最小数
2019-01-08 本文已影响0人
myFamily329
说明：记录刷剑指offer，使用php与python两种语言，对解题思路以及涉及到的基本语法以及知识点做学习记录。其中对于每道题目进行粗略的分类。
题目来源
- 分类：数组
- 把数组排成最小数
题目描述
输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
解题思路（参考剑指offer 第二版）
- 直接解法，所有数字全排列，然后把每个排列拼起来，最后求出拼起来的数字的最小值，n个数字总共有n!个排列，所以考虑另一种更快的算法。
注意点：
- 需要考虑一个潜在问题，m和n都在int型能表达的范围内，但把它们拼接起来的数字mn和nm用int型表示可能溢出（隐形的大数问题）
直观解决大数问题的方法就是把数字转换为字符串，把数字m和n拼接起来得到mn和nm，它们的位数肯定是相同的，因此比较它们的大小只需要按照字符串大小的比较规则就可以。
排序规则如下，我们需要先将数字转换成字符串再进行比较，因为需要串起来进行比较。比较完之后，按顺序输出即可。 - 若mn > nm 则 m 大于 n，
- 若mn < nm 则 m 小于 n，
- 若mn = nm 则 m 等于 n；
编程实现
PHP
<?php
运行时间：70ms
占用内存：2752k
function PrintMinNumber($numbers)
{
if(empty($numbers) || count($numbers) <= 0){
return "";
}
usort($numbers, 'ReSorted');
$res = "";
for($i = 0; $i < count($numbers); $i++){
$res .= $numbers[$i];
}
return $res;
}
function ReSorted($str1, $str2){
$strA = $str1.$str2;
$strB = $str2.$str1;
// 如果第一个数大于第二个数 1
return ($strA < $strB)? -1 : 1 ;
}
var_dump(PrintMinNumber(array(3, 32, 321)));
?>
Python
运行时间：30ms
占用内存：5728k
# -*- coding:utf-8 -*-
class Solution:
def PrintMinNumber(self, numbers):
# write code here
if not numbers:
return ''
string = [str(num) for num in numbers]
string.sort(self.theMax,reverse=False)
return ''.join(string)
def theMax(self,str1,str2):
str1str2 = str1+str2
str2str1 = str2+str1
return 1 if str1str2 > str2str1 else -1
#另一种方法
# -*- coding:utf-8 -*-
class Solution:
def PrintMinNumber(self, numbers):
if not numbers or len(numbers) <= 0:
return ''
compares = lambda x, y : cmp(str(x) + str(y), str(y) + str(x))
# python2.7
min_string = sorted(numbers, cmp = compares)
return ''.join(str(s) for s in min_string)
s = Solution()
print(s.PrintMinNumber([3, 32, 321]))
知识总结复习
- php默认排序函数
- sort() 从小到大 （可以以数字/字符串的形式比较）
- resort() 从大到小 （同上）
- usort() 自定义的排序函数
https://www.cnblogs.com/leekale/p/4662736.html
usort两两提取数组中的数值，并按顺序输入自定义函数中，自定义函数根据内容返回1或者-1；usort根据返回值为1或者-1，得到传入的数值1“大于”或者“小于”数值2，然后对数值进行从小到大的排序。即：返回值为1，说明数值1“大于”数值2，然后排序：数值2—>数值1；返回值为-1，说明数值1“小于”数值2，然后排序：数值1->数值2。
- php字符串的拼接
- 直接用.来进行连接.
- 用.=进行连接。
- 先压入数组，再通过join函数连接。
- python 数值转换为字符串函数
- str()
- python匿名函数 lambda()
参考学习：https://www.cnblogs.com/hf8051/p/8085424.html - python排序函数sort() 与 sorted()
- sorted()不会改变原来的list，而是会返回一个新的已经排序好的list
- list.sort()方法仅仅被list所定义，sorted()可用于任何一个可迭代对象
参考学习：https://www.cnblogs.com/ShaunChen/p/6205330.html
