admin 管理员组文章数量: 1086019
golang 数组组合成最小的整数
其实这道题的本质是一个排序问题.不管求最大还是最小, 我们都可以使用排序算法解决. 普通排序是升序还是降序,主要看交互比较代码,这里求最小值相当于一个升级, 求最大值相当于一个降序.
这道题的特殊就在于求数组所有数字组成在一起最小值.如12和9, 直接观察就能看出129比912要小, 所以我们排序可以抽象为m与n两个数据,相当于mn与nm相比.再结合使用快速排序或冒泡排序都可以啦. 关键在于这个比较函数的操作.
golang 语言实现
核心: 比较函数代码
//核心函数
// 如 9, 12. 我们需要做912与129的比较, 显然912>129
//如果ab < ba 的话则返回true,否则返回false
func cmp(a, b int) bool {
if a == b {
return false
}
sa := strconv.Itoa(a)
sb := strconv.Itoa(b)
sa2 := sa + sb
sb2 := sb + sa
ma, err := strconv.Atoi(sa2)
if err != nil {
log.Fatal("a params transfer failed")
return false
}
nb, err := strconv.Atoi(sb2)
if err != nil {
log.Fatal("b params transfer failed")
return false
}
fmt.Printf("m:%d,n:%d\n", ma,nb)
if ma > nb { //相当于mn > nm 将最小的元素置换到最前面.如果是小于则最大元素置换到最前面.
return true
}
return false
}
介绍三种方法实现.
1.sort.Slice
时间复杂度:O(Nlogn)
//利用系统自带排序函数
func MinNumberBySort(numbers []int) string {
if len(numbers) == 0 {
return ""
}
sort.Slice(numbers, func(i, j int) bool {
return !cmp(numbers[i], numbers[j])
})
build := strings.Builder{}
for _, v := range numbers {
build.WriteString(strconv.Itoa(v))
}
return build.String()
}
2. 冒泡方法
时间复杂度O(n^2)
//冒泡方法, 时间复杂度O(n^2)
func PrintMinNumberByBubbling(numbers []int) string {
length := len(numbers)
for i := 0; i < length; i ++ {
for j := 0; j < length-1-i; j++ {
if cmp(numbers[j], numbers[j+1]) {
numbers[j], numbers[j+1] = numbers[j+1], numbers[j]
}
}
}
build := strings.Builder{}
for _, v := range numbers {
build.WriteString(strconv.Itoa(v))
}
return build.String()
}
3.快速排序
//快排实现
func MinNumbersByQuickSort(numbers []int) string {
qSort(numbers, 0, len(numbers)-1)
build := strings.Builder{}
for _, v := range numbers {
build.WriteString(strconv.Itoa(v))
}
return build.String()
}
//快排
func qSort(arr []int, left, right int) {
i, j := left, right
pivot := arr[left]
for left < right {
for left < right && cmp(arr[right], pivot) {//比较大小, 大于中间值的不移动,反之移动.
right --
}
arr[left] = arr[right]
for left < right && cmp(pivot, arr[left]) {//比较大小, 小于中间值的不移动.反之移动
left ++
}
arr[right] = arr[left]
}
arr[left] = pivot
if left - i > 1 {
qSort(arr, i, left-1)
}
if j - left > 1 {
qSort(arr, left+1, j)
}
}
测试用例
func TestPrintMinNumber(t *testing.T) {
src.Asset(1, t, "10211516279", PrintMinNumberByBubbling([]int {16,27,15,9,102, 1}))
src.Asset(2, t, "1516279", PrintMinNumberByBubbling([]int{16,15,27,9}))
}
func TestMinNumber(t *testing.T) {
src.Asset(1, t, "10211516279", MinNumberBySort([]int {16,27,15,9,102, 1}))
src.Asset(2, t, "1516279", MinNumberBySort([]int{16,15,27,9}))
}
func TestMinNumbersByQuickSort(t *testing.T) {
src.Asset(1, t, "10211516279", MinNumbersByQuickSort([]int {16,27,15,9,102, 1}))
src.Asset(2, t, "1516279", MinNumbersByQuickSort([]int{16,15,27,9}))
}
本文标签： golang 数组组合成最小的整数
版权声明：本文标题：golang 数组组合成最小的整数 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1688024152a170077.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论