Golang升序

Question

我在这里有一个 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

Answer 1

这个问题有点棘手：它不要求您对整个切片（或 mangkuk 在它自己的术语中）进行排序；它要求您首先识别称为 sudu 的所有连续间隔（可能有重复元素），然后对每个 sudu 进行排序。func makeCawan(mangkuk []int) []int {&nbsp; &nbsp; for now, n := 0, len(mangkuk); now < n; {&nbsp; &nbsp; &nbsp; &nbsp; min := mangkuk[now]&nbsp; &nbsp; &nbsp; &nbsp; max := min&nbsp; &nbsp; &nbsp; &nbsp; head := now&nbsp; &nbsp; loop:&nbsp; &nbsp; &nbsp; &nbsp; for now++; now < n; now++ {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; switch x := mangkuk[now]; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; case x < min-1 || x > max+1:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; sort(mangkuk[head:now], min, max)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break loop&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; case x == min-1:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; min = x&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; case x == max+1:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; max = x&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; if now >= n {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; sort(mangkuk[head:now], min, max)&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return mangkuk}游乐场：https://play.golang.org/p/z3TGWnWnrVY

Answer 2

回答这个问题假设你想对连续和重复的 int 切片进行排序。简单地对切片进行排序是一种可读的解决方案，但是对于长度为 n 的切片使用基于比较的排序算法需要 O(nlgn)。我们可以使用具有 O(n) 辅助空间的性能更好的算法。算法：1. 迭代数组 A 并找到最小值和最大值。2. 创建一个长度为 max-min+1 的数组 B。3. 遍历 A 并将每个元素的计数存储在 B 中，即B[A[i] - min]++。4. 现在遍历 B 并打印&nbsp;i + minB[i] 次。时间复杂度 - O(n)https://play.golang.org/p/rptgMpWdKCX请注意，此循环也是 O(n)，其中 n 是实际输入数组的长度。for i:=0;i<len(b);i++{&nbsp; &nbsp; &nbsp; &nbsp; for b[i] != 0{&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; fmt.Printf("%v ", i + min)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; b[i]--&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }