Голанг по возрастанию

Question

У меня есть вопрос по языку Go, есть ли лучший способ ответить на него в коде Golang по сравнению с моим ниже?

Mangkuk - список, состоящий из максимального размера Sudu.Суду - это перестановка последовательных целых чисел, возможно, с повторяющимися элементами.

Каван - это Мангкук, где каждый Суду отсортирован в порядке возрастания.Напишите функцию MakeCawan (→ Mangkuk) для сортировки данного Mangkuk в 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

Answer 1

Проблема немного хитрая: она не просит вас отсортировать весь фрагмент (или mangkuk в его собственном термине);он просит вас сначала распознать все последовательные интервалы (с возможными повторяющимися элементами), которые называются sudu, а затем отсортировать каждый sudu.

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
}

Playground: https://play.golang.org/p/z3TGWnWnrVY

Answer 2

Отвечая на этот вопрос, предполагая, что вы хотите отсортировать фрагмент int, который является последовательным и повторяющимся.

Простая сортировка фрагмента является читаемым решением, но для O (nlgn) используется алгоритм сортировки на основе сравнения длясрез длиной n.

Мы можем использовать более эффективный алгоритм с O (n) вспомогательным пространством.Алгоритм:
1. Выполните итерацию по массиву A и найдите минимальное и максимальное значения.
2. Создайте массив B длиной max-min + 1.
3. Выполните итерацию по A и сохраните счетчик каждого элемента вB т.е. B[A[i] - min]++.
4. Теперь переберите B и напечатайте i + min, B [i] раз.

Сложность времени - O (n)

https://play.golang.org/p/rptgMpWdKCX

Обратите внимание, что этот цикл также равен O (n), где n - длина фактического входного массива.

for i:=0;i<len(b);i++{
        for b[i] != 0{
            fmt.Printf("%v ", i + min)
            b[i]--
        }
    }