剑指offer面试题45：把数组排成最小的数（golang实现）

题目描述

输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

示例1：

输入: [10,2]
输出: "102"

示例2

输入: [3,30,34,5,9]
输出: "3033459"

限制

0 < nums.length <= 100

算法分析

• 将int数组转化为string数组后，对数组进行排序。排序规则为若a + b > b + a，则a > b，否则 b > a。排序结束将字符串按顺序拼接即可。

复杂度分析

问题规模为数组大小n

• 时间复杂度：O( n l o g n nlogn nlogn)，sort.Sort()排序的时间复杂度为nlogn。
• 空间复杂度：O( n n n)，用到了一个string数组。

Golang代码如下

type StringSlice []string

func (s StringSlice) Len() int {
	return len(s)
}

func (s StringSlice) Less(i, j int) bool {
	n1, _ := strconv.Atoi(s[i] + s[j])
	n2, _ := strconv.Atoi(s[j] + s[i])
	if n1 < n2 {
		return true
	} else {
		return false
	}
}

func (s StringSlice) Swap(i, j int) {
	s[i], s[j] = s[j], s[i]
}

func minNumber(nums []int) (res string) {
	str := make([]string, len(nums))
	for i := 0; i < len(nums); i++ {
		str[i] = strconv.Itoa(nums[i])
	}
	sort.Sort(StringSlice(str))
	for i := 0; i < len(str); i++ {
		res += str[i]
	}
	return
}