algorithm - 如何在golang中按字符a对字符串数组进行排序

Question

我正在研究一个算法问题，我需要用 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 的数量为偶数，则按长度排序，按降序排列，但逻辑上我被困在这里。

Answer 1

使用sort.Slice()按自定义逻辑对任何 slice 进行排序。此函数需要一个定义两个元素之间“较少”关系的函数。

在您的情况下，如果一个值包含更多 a 字符，或者计数相等，则该值小于另一个值，然后比较它们的长度。要计算子字符串，请使用 strings.Count() 。要获取字符串的长度，请使用内置 len()函数，但请注意 len() 返回 UTF-8 编码的字节长度，而不是 rune 数量。对于信件，请使用 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 且具有相同长度的元素之间的顺序是未指定的。如果您希望它们的顺序与输入 slice 中的顺序相同，请使用 sort.SliceStable()而不是 sort.Slice()。

另请注意，我们的自定义逻辑并不复杂，但也不简单。该函数可能会被多次调用来比较元素，并且同一元素可能会被多次传递(询问)。如果输入 slice 很大，那么为每个元素计算一次 a 的数量和 rune 长度，将它们存储在例如映射中，然后只需在中查询此预先计算的数据可能会有利可图。 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 .