剑指 Offer 45. 把数组排成最小的数
https://leetcode-cn.com/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/
1.输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
2.点击题目查看具体要求，并且输入输出[1].
输出结果可能非常大，所以你需要返回一个字符串而不是整数拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0
输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
1.输入: [10,2]
输出: "102"
2.输入: [3,30,34,5,9]
输出: "3033459"
3.解题思路：
①暴力法：时间复杂度o(n²) 空间复杂度o(1),空间上虽然为常数，但是时间需要更多的消耗。pass
②排序法：首先只要数字的字符串符合a b > b a，则b放在a的前面就行了， 如下图。虽然是全排列问题，但是本质上是个排序问题。
4.解答[1]
func minNumber(nums []int) string {
strs := make([]string, len(nums), len(nums)+1)
for i, v := range nums {
strs[i] = strconv.Itoa(v)
}
for i := 0; i < len(strs); i++ {
for j := i+1; j < len(strs); j++ {
mn, _ := strconv.Atoi(strs[i] + strs[j])
nm, _ := strconv.Atoi(strs[j] + strs[i])
if nm < mn {
strs[i], strs[j] = strs[j], strs[i]
}
// fmt.Println("mn:", mn, "nm:", nm, "strs:", strs)
}
}
strRet := ""
for _, v := range strs {
strRet += v
}
return strRet
}
5.结果
为啥呢么12ms，只击败了8.58%，建议使用快排解决，这样时间复杂度为O（lgN），凌晨1.35了，好累。挖个坑。
[1]https://www.cnblogs.com/Concho/p/3730874.html go语言冒泡排序代码
[2] 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/ 算法原理
