Как мне найти самые длинные строки в массиве?

Question

На самом деле я могу сделать это, используя два цикла в Go Language, например, если у меня есть массив как:

["aa", "aab", "bcd", "a", "cdf", "bb"]

Мне нужно вернуть строки с maxLength.Таким образом, вывод будет:

["aab", "bcd", "cdf"]

Вот что я делаю.

package main

import "fmt"

func allLongestStrings(inputArray []string) []string {
    maxLength := len(inputArray[0])
    outputArray := []string{}
    for _, value := range inputArray {
        if len(value) > maxLength {
            maxLength = len(value)
        }
    }
    for _, val := range inputArray {
        if len(val) == maxLength {
            outputArray = append(outputArray, val)
        }
    }
    return outputArray
}

func main() {
    xs := []string{"aa", "aab", "bcd", "a", "cdf", "bb"}
    fmt.Println(allLongestStrings(xs))
}

Возможно ли сделать это за один цикл, потому что я выполняю один и тот же цикл дважды, чтобы найти длину идобавить строки в выходной массив.

Заранее спасибо.

Answer 1

Я бы сделал это с помощью пакета сортировки.По сути, вы создаете пользовательскую функцию сортировки, реализуя sort.Interface и используете sort.Sort в ваших интересах.

package main

import "sort"
import "fmt"

type sortByLength []string

// Len implements Len of sort.Interface
func (s sortByLength) Len() int {
   return len(s)
}

// Swap implements Swap of sort.Interface
func (s sortByLength) Swap(i, j int) {
   s[i], s[j] = s[j], s[i]
}

// Less implements Less of sort.Interface
func (s sortByLength) Less(i, j int) bool {
    return len(s[i]) > len(s[j])
}

func main() {
    toFind := []string{"aa", "aab", "bcd", "a", "cdf", "bb"}

    // We sort it by length, descending
    sort.Sort(sortByLength(toFind))

    // The first element is sure to be the longest
    longest := []string{toFind[0]}

    // In case we have more than one element in toFind...
    if len(toFind) > 1 {

        // ...we need to find all remaining elements of toFind...
        for _, str := range toFind[1:] {

            // ...which are not smaller than the first element of longest.
            if len(str) < len(longest[0]) {

                // In case the current element is smaller in length, we can stop iterating
                // over toFind.
                break
            }

            // We know that str has the same length as longest[0], so we append it
            longest = append(longest, str)

        }
    }
    fmt.Println(longest)
}

Запустите его на игровой площадке

Однако, хотя в вашем собственном коде имеется только один цикл, сортировка, очевидно, выполняет и входные данные.

Answer 2

Например, более эффективная версия решения @ ThunderCat ,

package main

import "fmt"

func longest(a []string) []string {
    var l []string
    if len(a) > 0 {
        l = append(l, a[0])
        a = a[1:]
    }
    for _, s := range a {
        if len(l[0]) <= len(s) {
            if len(l[0]) < len(s) {
                l = l[:0]
            }
            l = append(l, s)
        }
    }
    return append([]string(nil), l...)
}

func main() {
    a := []string{"aa", "aab", "bcd", "a", "cdf", "bb"}
    fmt.Println(len(a), a)
    l := longest(a)
    fmt.Println(len(l), cap(l), l)
}

Детская площадка: https://play.golang.org/p/JTvl4wVvSEK

Вывод:

6 [aa aab bcd a cdf bb]
3 4 [aab bcd cdf]

---

Чтение @ решения ThunderCat , есть возможности для улучшения.Например, для проблем с максимумом и минимумом избегайте использования специальных значений в качестве начального максимального или минимального значения.Не перераспределяйте память и не оставляйте висячие указатели.

Go string реализован следующим образом:

type stringStruct struct {
    str unsafe.Pointer
    len int
}

Если список состоит из 1000 строк длиной 1000, за которыми следует одинстрока длиной 1 001, возвращаемый список будет иметь длину один и емкость не менее 1000.999 записей имеют висячие указатели на 1000 строк байтов, которые Go gc не сможет освободить, тратя более одного мегабайта.

package main

import (
    "fmt"
    "strings"
    "unsafe"
)

type stringStruct struct {
    str unsafe.Pointer
    len int
}

func main() {
    var l []string
    for n := 0; n < 1000; n++ {
        l = append(l, strings.Repeat("x", 1000))
    }
    l = l[:0]
    l = append(l, strings.Repeat("y", 1001))

    over := (cap(l) - len(l)) * int(unsafe.Sizeof(stringStruct{}))
    for i, o := len(l), l[:cap(l)]; i < cap(l); i++ {
        over += len(o[i])
    }
    fmt.Println(over) // 1015368 bytes 64-bit, 1007184 bytes 32-bit 
}

Детская площадка: https://play.golang.org/p/Fi7EgbvdVkp

---

Для программычтобы быть правильным, он должен быть читаемым.Во-первых, напишите фундаментальные алгоритмы без отвлечения ошибок или особых случаев.

var l []string
for _, s := range a {
    if len(l[0]) <= len(s) {
        if len(l[0]) < len(s) {
            l = l[:0]
        }
        l = append(l, s)
    }
}

Далее добавьте особые случаи, не прерывая работу основного алгоритма.В этом случае обрабатывайте списки нулевой и одной длины.

var l []string
if len(a) > 0 {
    l = append(l, a[0])
    a = a[1:]
}
for _, s := range a {
    if len(l[0]) <= len(s) {
        if len(l[0]) < len(s) {
            l = l[:0]
        }
        l = append(l, s)
    }
}

Наконец, убедитесь, что функция эффективна как для ЦП, так и для памяти.Распределение является точным, и нет никаких висячих указателей на неиспользуемые строки.

var l []string
if len(a) > 0 {
    l = append(l, a[0])
    a = a[1:]
}
for _, s := range a {
    if len(l[0]) <= len(s) {
        if len(l[0]) < len(s) {
            l = l[:0]
        }
        l = append(l, s)
    }
}
return append([]string(nil), l...)

Answer 3

Попробуйте:

func allLongestStrings(inputArray []string) []string {
    max := -1 // -1 is guaranteed to be less than length of string
    var result []string
    for _, s := range inputArray {
        if len(s) < max {
            // Skip shorter string
            continue
        }
        if len(s) > max {
            // Found longer string. Update max and reset result.
            max = len(s)
            result = result[:0]
        }
        // Add to result
        result = append(result, s)
    }
    return result
}

Как указывает peterSO в другом ответе, результирующий срез может иметь емкость, превышающую требуемую, и может содержать строковые значения, превышающие длину среза.Дополнительное распределение и ссылки на строки могут быть проблемой в некоторых контекстах (результат сохраняется в течение длительного времени, строки большие, ...).Возвращает копию среза , если выделение и ссылки являются проблемой.

func allLongestStrings(inputArray []string) []string {
    ...
    return append([]string(nil), result...)
}

Если функция может изменять исходный срез, то результат функции может быть создан во входном срезе,Это позволяет избежать выделения результирующего среза.

func allLongestStrings(inputArray []string) []string {
    n := 0
    max := -1
    for i, s := range inputArray {
        if len(s) < max {
            // Skip shorter string
            continue
        }
        if len(s) > max {
            // Found longer string. Update max and reset result.
            max = len(s)
            n = 0
        }
        inputArray[n], inputArray[i] = inputArray[i], inputArray[n]
        n++
    }
    return inputArray[:n]
}