我在這里有一個 Go 語言問題，與下面我的相比，有沒有更好的方法來回答編碼 Golang 的答案？Mangkuk 是由最大尺寸的 Sudu 組成的列表。Sudu 是連續(xù)整數(shù)的排列，可能包含重復項。Cawan 是 Mangkuk，其中每個 Sudu 都按升序排序。編寫一個函數(shù) 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
2 回答
胡子哥哥
TA貢獻1825條經(jīng)驗 獲得超6個贊
這個問題有點棘手：它不要求您對整個切片（或 mangkuk 在它自己的術語中）進行排序；它要求您首先識別稱為 sudu 的所有連續(xù)間隔（可能有重復元素），然后對每個 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
慕工程0101907
TA貢獻1887條經(jīng)驗 獲得超5個贊
回答這個問題假設你想對連續(xù)和重復的 int 切片進行排序。
簡單地對切片進行排序是一種可讀的解決方案，但是對于長度為 n 的切片使用基于比較的排序算法需要 O(nlgn)。
我們可以使用具有 O(n) 輔助空間的性能更好的算法。算法：
1. 迭代數(shù)組 A 并找到最小值和最大值。
2. 創(chuàng)建一個長度為 max-min+1 的數(shù)組 B。
3. 遍歷 A 并將每個元素的計數(shù)存儲在 B 中，即B[A[i] - min]++。
4. 現(xiàn)在遍歷 B 并打印 i + minB[i] 次。
時間復雜度 - O(n)
https://play.golang.org/p/rptgMpWdKCX
請注意，此循環(huán)也是 O(n)，其中 n 是實際輸入數(shù)組的長度。
for i:=0;i<len(b);i++{
for b[i] != 0{
fmt.Printf("%v ", i + min)
b[i]--
}
}
- 2 回答
- 0 關注
- 150 瀏覽
添加回答
舉報
0/150
提交
取消