How can I sort string array by character a in golang-CodePudding

I am working on an algorithm question and I need to encode it with golang. In this question I need to sort a given string array by character 'a'. If I need to talk about the details of the question.

Question:

 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

Input

["aaaasd", "a", "aab", "aaabcd", "ef", "cssssssd", "fdz", "kf", "zc", "lklklklklklklklkl", "l"]

Output:

["aaaasd", "aaabcd", "aab", "a", "lklklklklklklklkl", "cssssssd", "fdz", "ef", "kf", "zc", "l"]

My Solution:

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
}

I'm currently getting the number of a and the length of each element in it. I need to sort first by the number of a, then by length if there are even numbers of a, in descending order, but logically I'm stuck here.

CodePudding user response：

Use sort.Slice() to sort any slice by a custom logic. This function expects a function that defines the "less" relation between 2 elements.

In your case a value is less than another if it contains more a characters, or if the count is equal, then resort to comparing their lengths. To count substrings, use strings.Count(). To get the length of a string, use the builtin len() function, but note that len() returns the UTF-8 encoded byte length, not the number of runes. For the letter, use utf8.RuneCountInString().

For example:

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)

This will output (try it on the Go Playground):

[aaaasd aaabcd aab a lklklklklklklklkl cssssssd fdz ef kf zc l]

Note that the order between elements that contain equal number of a's and have equal length is unspecified. If you want them in the same order as in your input slice, use sort.SliceStable() instead of sort.Slice().

Also note that our custom logic is not complex but not trivial either. The function may be called many times to compare elements, and the same element may be passed (asked) multiple times. If the input slice is big, it may be profitable to calculate the numer of a's and the rune length once for each element, store them in map for example, and just query this precalculated data in the less() function.

This is how it could look like:

// 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
})

This outputs the same. Try it on the Go Playground.