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