[剑指-33](php&python):把数组排成最小数

说明：记录刷剑指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]))

知识总结复习

1. 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。

2. php字符串的拼接

• 直接用.来进行连接.
• 用.=进行连接。
• 先压入数组，再通过join函数连接。

3. python 数值转换为字符串函数

• str()

4. python匿名函数 lambda()
   参考学习：https://www.cnblogs.com/hf8051/p/8085424.html
5. python排序函数sort() 与 sorted()

• sorted()不会改变原来的list，而是会返回一个新的已经排序好的list
• list.sort()方法仅仅被list所定义，sorted()可用于任何一个可迭代对象
  参考学习：https://www.cnblogs.com/ShaunChen/p/6205330.html