我正在研究一個演算法問題，我需要用 golang 對其進行編碼。在這個問題中，我需要按字符“a”對給定的字串陣列進行排序。如果我需要談談問題的細節。
問題：
Write a function that sorts a bunch of words by the number of character “a”s within the
word (decreasing order). If some words contain the same amount of character “a”s then you
need to sort those words by their lengths
輸入
["aaaasd", "a", "aab", "aaabcd", "ef", "cssssssd", "fdz", "kf", "zc", "lklklklklklklklkl", "l"]
輸出：
["aaaasd", "aaabcd", "aab", "a", "lklklklklklklklkl", "cssssssd", "fdz", "ef", "kf", "zc", "l"]
我的解決方案：
func main() {
arr := []string{"aaaasd", "a", "aab", "aaabcd", "ef", "cssssssd", "fdz", "kf", "zc", "lklklklklklklklkl", "l"}
fmt.Println(mostFrequent(arr))
}
type FrequencyAndLength struct {
slice string
mostFrequent int
len int
}
func mostFrequent(arr []string) []FrequencyAndLength { // assuming no
testArray := []FrequencyAndLength{}
for _, a := range arr {
testArray = append(testArray, FrequencyAndLength{
slice: a,
mostFrequent: strings.Count(a, "a"),
len: len(a),
})
}
fmt.Println(testArray)
return testArray
}
我目前正在獲取 a 的數量和其中每個元素的長度。我需要先按 a 的數量排序，如果有偶數 a，則按長度按降序排列，但從邏輯上講，我被困在這里。
uj5u.com熱心網友回復：
用于sort.Slice()按自定義邏輯對任何切片進行排序。該函式需要一個定義兩個元素之間“較少”關系的函式。
a在您的情況下，如果一個值包含更多字符，或者計數相等，則該值小于另一個值，則訴諸比較它們的長度。要計算子字串，請使用strings.Count(). 要獲取 a 的長度string，請使用內置len()函式，但請注意，它len()回傳的是 UTF-8 編碼的位元組長度，而不是符文數。對于字母，使用utf8.RuneCountInString().
例如：
in := []string{"aaaasd", "a", "aab", "aaabcd", "ef", "cssssssd", "fdz", "kf", "zc", "lklklklklklklklkl", "l"}
sort.Slice(in, func(i, j int) bool {
s1, s2 := in[i], in[j]
count1, count2 := strings.Count(s1, "a"), strings.Count(s2, "a")
if count1 != count2 {
return count1 > count2
}
return utf8.RuneCountInString(s1) > utf8.RuneCountInString(s2)
})
fmt.Println(in)
這將輸出（在Go Playground上嘗試）：
[aaaasd aaabcd aab a lklklklklklklklkl cssssssd fdz ef kf zc l]
請注意，包含相等數量a和長度的元素之間的順序是未指定的。如果您希望它們與輸入切片中的順序相同，請使用sort.SliceStable()而不是sort.Slice().
另請注意，我們的自定義邏輯并不復雜，但也不是微不足道的。該函式可能會被多次呼叫以比較元素，并且同一元素可能會被多次傳遞（詢問）。如果輸入的 slice 很大，那么a為每個元素計算一次 's 的數量和 rune 長度可能是有利可圖的，例如將它們存盤在 map 中，然后在less()函式中查詢這些預先計算的資料。
這就是它的樣子：
// Pre-calculate
type info struct{ count, length int }
calculated := map[string]info{}
for _, s := range in {
calculated[s] = info{
count: strings.Count(s, "a"),
length: utf8.RuneCountInString(s),
}
}
sort.Slice(in, func(i, j int) bool {
inf1, inf2 := calculated[in[i]], calculated[in[j]]
if inf1.count != inf2.count {
return inf1.count > inf2.count
}
return inf1.length > inf2.length
})
這輸出相同。在Go Playground上嘗試一下。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/513872.html
標籤：算法排序去