Go 升序

一分耕耘，一分收获！既然打开了这篇文章《Go 升序》，就坚持看下去吧！文中内容包含等等知识点...希望你能在阅读本文后，能真真实实学到知识或者帮你解决心中的疑惑，也欢迎大佬或者新人朋友们多留言评论，多给建议！谢谢！

我这里有一个 go 语言问题，与下面我的相比，在 golang 编码中是否有更好的方法来回答答案？

mangkuk 是由最大尺寸 sudu 组成的列表。 sudu 是连续整数的排列，可能包含重复项。

cawan 是 mangkuk，其中每个 sudu 按升序排序。 编写一个函数 makecawan(→mangkuk)，将给定的 mangkuk 排序到 cawan 中。

for example,
makecawan([21, 20, 18, 20, 18, 20, 19]),
makecawan([21, 2000000, 18, 20, 18, 20, 19]),
makecawan([21, 20, 18, 20, 18, 20, 1900000])
should produce, respectively,
[18, 18, 19, 20, 20, 20, 21],
[21, 2000000, 18, 18, 19, 20, 20],
[20, 21, 18, 20, 18, 20, 1900000].

package main

    import (
    	"fmt"
    	"sort"
    )

    func main() {
    	sl := []string{"MakeCawan"}
    	sort.Sort(sort.StringSlice(sl))
    	fmt.Println(sl)
    	
    	sl1 := []string{"MakeCawan"}
    	sort.Sort(sort.StringSlice(sl1))
    	fmt.Println(sl1)
    	
    	sl2 := []string{"MakeCawan"}
    	sort.Sort(sort.StringSlice(sl2))
    	fmt.Println(sl2)
    	
    	intSlice := []int{21,20,18,20,18,20,19}
    	sort.Sort(sort.IntSlice(intSlice))
    	fmt.Println(intSlice)

    }

输出：

https://play.golang.org/p/tse0btmros_9

解决方案

这个问题有点棘手：它不会要求您对整个切片（或用它自己的术语来说是 mangkuk）进行排序；而是要求您对整个切片进行排序。它要求您首先识别所有连续的间隔（可能有重复的元素），称为 sudu，然后对每个 sudu 进行排序。

func makecawan(mangkuk []int) []int {
    for now, n := 0, len(mangkuk); now < n; {
        min := mangkuk[now]
        max := min
        head := now
    loop:
        for now++; now < n; now++ {
            switch x := mangkuk[now]; {
            case x < min-1 || x > max+1:
                sort(mangkuk[head:now], min, max)
                break loop
            case x == min-1:
                min = x
            case x == max+1:
                max = x
            }
        }
        if now >= n {
            sort(mangkuk[head:now], min, max)
        }
    }

    return mangkuk
}

演示：https://play.golang.org/p/z3TGWnWnrVY

回答这个问题假设你想对连续且重复的 int 切片进行排序。

简单地对切片进行排序是一种可读的解决方案，但对于长度为 n 的切片使用基于比较的排序算法需要 o(nlgn)。

我们可以使用具有 o(n) 辅助空间的更好性能算法。 算法：
1. 迭代数组 a 并找到其中的最小值和最大值。
2. 创建一个数组b，长度为max-min+1。
3. 迭代 a 并将每个元素的计数存储在 b 中 即 b[a[i] - min]++ 。
4. 现在迭代 b 并打印 i + min, b[i] 次。

时间复杂度 - o(n)

https://play.golang.org/p/rptgMpWdKCX

请注意，此循环也是 o(n)，其中 n 是实际输入数组的长度。

for i:=0;i<len(b);i++{
        for b[i] != 0{
            fmt.Printf("%v ", i + min)
            b[i]--
        }
    }

到这里，我们也就讲完了《Go 升序》的内容了。个人认为，基础知识的学习和巩固，是为了更好的将其运用到项目中，欢迎关注golang学习网公众号，带你了解更多关于的知识点！