December 14, 2021: rebuild the queue according to height. Suppose there's a bunch of people out of order

2021-12-14： Rebuild the queue according to height .

Let's say there's a group of people in a disordered order standing in a line , Array people Properties that represent some people in the queue （ Not necessarily in order ）. Every peoplei = hi, ki It means the first one i The height of an individual is hi , front Just right Yes ki Height greater than or equal to hi People who .

Please reconstruct and return the input array people The queue represented by . The returned queue should be formatted as an array queue , among queuej = hj, kj It's number one in the queue j Personal attributes （queue0 It's the people at the front of the line ）.

Power button 406.

answer 2021-12-14：

See code for details .golang There is something wrong with the code , Details can be viewed java Code .

The code to use golang To write . The code is as follows ：

package main

import (
    "fmt"
    "sort"
)

func main() {
    people := [][]int{{6, 0}, {5, 0}, {4, 0}, {3, 2}, {2, 2}, {1, 4}}
    ret := reconstructQueue2(people)
    fmt.Println(ret)
}

func reconstructQueue1(people [][]int) [][]int {
    N := len(people)
    units := make([]*Unit, N)
    for i := 0; i < N; i++ {
        units[i] = NewUnit(people[i][0], people[i][1])
    }
    sort.Slice(units, func(i, j int) bool {
        o1 := units[i]
        o2 := units[j]
        if o1.h != o2.h {
            return o2.h < o1.h
        } else {
            return o1.k > o2.k
        }
    })
    arrList := make([]*Unit, 0)
    for _, unit := range units {
        arrListCopy := arrList[0:unit.k]
        arrListCopy = append(arrListCopy, unit)
        arrListCopy = append(arrListCopy, arrList[unit.k:]...)
        arrList = arrListCopy
    }
    ans := make([][]int, N)
    for i := 0; i < N; i++ {
        ans[i] = make([]int, 2)
    }
    index := 0
    for _, unit := range arrList {
        ans[index][0] = unit.h
        ans[index][1] = unit.k
        index++
    }
    return ans
}

func reconstructQueue2(people [][]int) [][]int {
    N := len(people)
    units := make([]*Unit, N)
    for i := 0; i < N; i++ {
        units[i] = NewUnit(people[i][0], people[i][1])
    }
    sort.Slice(units, func(i, j int) bool {
        o1 := units[i]
        o2 := units[j]
        if o1.h != o2.h {
            return o2.h < o1.h
        } else {
            return o1.k > o2.k
        }
    })
    tree := &SBTree{}
    for i := 0; i < N; i++ {
        tree.insert(units[i].k, i)
    }
    allIndexes := tree.allIndexes()

    ans := make([][]int, N)
    for i := 0; i < N; i++ {
        ans[i] = make([]int, 2)
    }
    index := 0
    for _, arri := range *allIndexes {
        ans[index][0] = units[arri].h
        ans[index][1] = units[arri].k
        index++
    }
    return ans
}

type Unit struct {
    h int
    k int
}

func NewUnit(height, greater int) *Unit {
    ret := &Unit{}
    ret.h = height
    ret.k = greater
    return ret
}

type SBTNode struct {
    value int
    l     *SBTNode
    r     *SBTNode
    size  int
}

func NewSBTNode(arrIndex int) *SBTNode {
    ret := &SBTNode{}
    ret.value = arrIndex
    ret.size = 1
    return ret
}

func twoSelectOne(c bool, a, b int) int {
    if c {
        return a
    } else {
        return b
    }
}

type SBTree struct {
    root *SBTNode
}

func (this *SBTree) rightRotate(cur *SBTNode) *SBTNode {
    leftNode := cur.l
    cur.l = leftNode.r
    leftNode.r = cur
    leftNode.size = cur.size
    a := 0
    if cur.l != nil {
        a = cur.l.size
    }
    b := 0
    if cur.r != nil {
        b = cur.r.size
    }
    cur.size = a + b + 1
    return leftNode
}

func (this *SBTree) leftRotate(cur *SBTNode) *SBTNode {
    rightNode := cur.r
    cur.r = rightNode.l
    rightNode.l = cur
    rightNode.size = cur.size
    cur.size = (twoSelectOne(cur.l != nil, cur.l.size, 0)) + (twoSelectOne(cur.r != nil, cur.r.size, 0)) + 1
    return rightNode
}

func (this *SBTree) maintain(cur *SBTNode) *SBTNode {
    if cur == nil {
        return nil
    }
    leftSize := 0
    if cur.l != nil {
        leftSize = cur.l.size
    }
    leftLeftSize := 0
    if cur.l != nil && cur.l.l != nil {
        leftLeftSize = cur.l.l.size
    } else {
        leftLeftSize = 0
    }
    leftRightSize := 0
    if cur.l != nil && cur.l.r != nil {
        leftRightSize = cur.l.r.size
    }
    rightSize := 0
    if cur.r != nil {
        rightSize = cur.r.size
    }
    rightLeftSize := 0
    if cur.r != nil && cur.r.l != nil {
        rightLeftSize = cur.r.l.size
    }
    rightRightSize := 0
    if cur.r != nil && cur.r.r != nil {
        rightRightSize = cur.r.r.size
    }
    if leftLeftSize > rightSize {
        cur = this.rightRotate(cur)
        cur.r = this.maintain(cur.r)
        cur = this.maintain(cur)
    } else if leftRightSize > rightSize {
        cur.l = this.leftRotate(cur.l)
        cur = this.rightRotate(cur)
        cur.l = this.maintain(cur.l)
        cur.r = this.maintain(cur.r)
        cur = this.maintain(cur)
    } else if rightRightSize > leftSize {
        cur = this.leftRotate(cur)
        cur.l = this.maintain(cur.l)
        cur = this.maintain(cur)
    } else if rightLeftSize > leftSize {
        cur.r = this.rightRotate(cur.r)
        cur = this.leftRotate(cur)
        cur.l = this.maintain(cur.l)
        cur.r = this.maintain(cur.r)
        cur = this.maintain(cur)
    }
    return cur
}

func (this *SBTree) insert0(root *SBTNode, index int, cur *SBTNode) *SBTNode {
    if root == nil {
        return cur
    }
    root.size++
    leftAndHeadSize := 0
    if root.l != nil {
        leftAndHeadSize = root.l.size + 1
    } else {
        leftAndHeadSize = 1
    }
    if index < leftAndHeadSize {
        root.l = this.insert0(root.l, index, cur)
    } else {
        root.r = this.insert0(root.r, index-leftAndHeadSize, cur)
    }
    root = this.maintain(root)
    return root
}

func (this *SBTree) get0(root *SBTNode, index int) *SBTNode {
    leftSize := twoSelectOne(root.l != nil, root.l.size, 0)
    if index < leftSize {
        return this.get0(root.l, index)
    } else if index == leftSize {
        return root
    } else {
        return this.get0(root.r, index-leftSize-1)
    }
}

func (this *SBTree) process(head *SBTNode, indexes *[]int) {
    if head == nil {
        return
    }
    this.process(head.l, indexes)
    //indexes.addLast(head.value)
    *indexes = append(*indexes, head.value)
    this.process(head.r, indexes)
}

func (this *SBTree) insert(index, value int) {
    cur := NewSBTNode(value)
    if this.root == nil {
        this.root = cur
    } else {
        if index <= this.root.size {
            this.root = this.insert0(this.root, index, cur)
        }
    }
}

func (this *SBTree) get(index int) int {
    ans := this.get0(this.root, index)
    return ans.value
}

func (this *SBTree) allIndexes() *[]int {
    //LinkedList<Integer> indexes = new LinkedList<>();
    indexes := make([]int, 0)
    this.process(this.root, &indexes)
    return &indexes
}

The results are as follows ：

picture

---

Zuo Shen java Code