1649-CreateSortedArrayThroughInstructions.go

package main

// 1649. Create Sorted Array through Instructions
// Given an integer array instructions, you are asked to create a sorted array from the elements in instructions. 
// You start with an empty container nums. 
// For each element from left to right in instructions, insert it into nums. 
// The cost of each insertion is the minimum of the following:
//     The number of elements currently in nums that are strictly less than instructions[i].
//     The number of elements currently in nums that are strictly greater than instructions[i].

// For example, if inserting element 3 into nums = [1,2,3,5], the cost of insertion is min(2, 1) 
// (elements 1 and 2 are less than 3, element 5 is greater than 3) and nums will become [1,2,3,3,5].

// Return the total cost to insert all elements from instructions into nums. 
// Since the answer may be large, return it modulo 10^9 + 7

// Example 1:
// Input: instructions = [1,5,6,2]
// Output: 1
// Explanation: Begin with nums = [].
// Insert 1 with cost min(0, 0) = 0, now nums = [1].
// Insert 5 with cost min(1, 0) = 0, now nums = [1,5].
// Insert 6 with cost min(2, 0) = 0, now nums = [1,5,6].
// Insert 2 with cost min(1, 2) = 1, now nums = [1,2,5,6].
// The total cost is 0 + 0 + 0 + 1 = 1.

// Example 2:
// Input: instructions = [1,2,3,6,5,4]
// Output: 3
// Explanation: Begin with nums = [].
// Insert 1 with cost min(0, 0) = 0, now nums = [1].
// Insert 2 with cost min(1, 0) = 0, now nums = [1,2].
// Insert 3 with cost min(2, 0) = 0, now nums = [1,2,3].
// Insert 6 with cost min(3, 0) = 0, now nums = [1,2,3,6].
// Insert 5 with cost min(3, 1) = 1, now nums = [1,2,3,5,6].
// Insert 4 with cost min(3, 2) = 2, now nums = [1,2,3,4,5,6].
// The total cost is 0 + 0 + 0 + 0 + 1 + 2 = 3.

// Example 3:
// Input: instructions = [1,3,3,3,2,4,2,1,2]
// Output: 4
// Explanation: Begin with nums = [].
// Insert 1 with cost min(0, 0) = 0, now nums = [1].
// Insert 3 with cost min(1, 0) = 0, now nums = [1,3].
// Insert 3 with cost min(1, 0) = 0, now nums = [1,3,3].
// Insert 3 with cost min(1, 0) = 0, now nums = [1,3,3,3].
// Insert 2 with cost min(1, 3) = 1, now nums = [1,2,3,3,3].
// Insert 4 with cost min(5, 0) = 0, now nums = [1,2,3,3,3,4].
// ​​​​​​​Insert 2 with cost min(1, 4) = 1, now nums = [1,2,2,3,3,3,4].
// ​​​​​​​Insert 1 with cost min(0, 6) = 0, now nums = [1,1,2,2,3,3,3,4].
// ​​​​​​​Insert 2 with cost min(2, 4) = 2, now nums = [1,1,2,2,2,3,3,3,4].
// The total cost is 0 + 0 + 0 + 0 + 1 + 0 + 1 + 0 + 2 = 4.

// Constraints:
//     1 <= instructions.length <= 10^5
//     1 <= instructions[i] <= 10^5

import "fmt"
import "sort"

// 超出时间限制 64 / 65
func createSortedArray(instructions []int) int {
    res, nums := 0, make([]int, len(instructions))
    for i, num := range instructions {
        left  := sort.Search(i, func(i int) bool { return nums[i] >= num })
        right := sort.Search(i, func(i int) bool { return nums[i] > num })
        res += min(left, i - right)
        copy(nums[right + 1:i + 1], nums[right:i + 1])
        nums[right] = num
    }
    return res % 1_000_000_007
}

func createSortedArray1(instructions []int) int {
    res, n, mod := 0, len(instructions), 1_000_000_007
    bit := NewBIT(100002)
    min := func (x, y int) int { if x < y { return x; }; return y; }
    for i := 0; i < n; i++ {
        lsum, rsum := bit.Query(instructions[i] - 1), i - bit.Query(instructions[i])
        res += min(lsum, rsum)
        res %= mod
        bit.Update(instructions[i], 1)
    }
    return res % mod
}

// Binary Tree Implementation 
type BIT struct {
    tree []int
    size int
}

func NewBIT(size int) *BIT {
    return &BIT{ make([]int, size), size, }
}

func (this *BIT) Update(index, val int) {
    for ; index <= this.size; index += index & -index {
        this.tree[index] += val
    }
}

func (this *BIT) Query(index int) int {
    sum := 0
    for ; index > 0; index -= index & -index {
        sum += this.tree[index]
    }
    return sum
}

func main() {
    // Example 1:
    // Input: instructions = [1,5,6,2]
    // Output: 1
    // Explanation: Begin with nums = [].
    // Insert 1 with cost min(0, 0) = 0, now nums = [1].
    // Insert 5 with cost min(1, 0) = 0, now nums = [1,5].
    // Insert 6 with cost min(2, 0) = 0, now nums = [1,5,6].
    // Insert 2 with cost min(1, 2) = 1, now nums = [1,2,5,6].
    // The total cost is 0 + 0 + 0 + 1 = 1.
    fmt.Println(createSortedArray([]int{1,5,6,2})) // 1
    // Example 2:
    // Input: instructions = [1,2,3,6,5,4]
    // Output: 3
    // Explanation: Begin with nums = [].
    // Insert 1 with cost min(0, 0) = 0, now nums = [1].
    // Insert 2 with cost min(1, 0) = 0, now nums = [1,2].
    // Insert 3 with cost min(2, 0) = 0, now nums = [1,2,3].
    // Insert 6 with cost min(3, 0) = 0, now nums = [1,2,3,6].
    // Insert 5 with cost min(3, 1) = 1, now nums = [1,2,3,5,6].
    // Insert 4 with cost min(3, 2) = 2, now nums = [1,2,3,4,5,6].
    // The total cost is 0 + 0 + 0 + 0 + 1 + 2 = 3.
    fmt.Println(createSortedArray([]int{1,2,3,6,5,4})) // 3
    // Example 3:
    // Input: instructions = [1,3,3,3,2,4,2,1,2]
    // Output: 4
    // Explanation: Begin with nums = [].
    // Insert 1 with cost min(0, 0) = 0, now nums = [1].
    // Insert 3 with cost min(1, 0) = 0, now nums = [1,3].
    // Insert 3 with cost min(1, 0) = 0, now nums = [1,3,3].
    // Insert 3 with cost min(1, 0) = 0, now nums = [1,3,3,3].
    // Insert 2 with cost min(1, 3) = 1, now nums = [1,2,3,3,3].
    // Insert 4 with cost min(5, 0) = 0, now nums = [1,2,3,3,3,4].
    // ​​​​​​​Insert 2 with cost min(1, 4) = 1, now nums = [1,2,2,3,3,3,4].
    // ​​​​​​​Insert 1 with cost min(0, 6) = 0, now nums = [1,1,2,2,3,3,3,4].
    // ​​​​​​​Insert 2 with cost min(2, 4) = 2, now nums = [1,1,2,2,2,3,3,3,4].
    // The total cost is 0 + 0 + 0 + 0 + 1 + 0 + 1 + 0 + 2 = 4.
    fmt.Println(createSortedArray([]int{1,3,3,3,2,4,2,1,2})) // 4

    fmt.Println(createSortedArray1([]int{1,5,6,2})) // 1
    fmt.Println(createSortedArray1([]int{1,2,3,6,5,4})) // 3
    fmt.Println(createSortedArray1([]int{1,3,3,3,2,4,2,1,2})) // 4
}