Leetcode 436. 寻找右区间

Leetcode 436. 寻找右区间

1. 问题描述

2. 思路

1. 遍历intervals数组，对于intervals[i]
   1.1 查找满足intervals[][0] >= intervals[i][1]的元素对应的索引index
   1.2 收集index

1.1中的查找过程，有多种方式，可以线性查找，也可以进行二分查找。如果使用二分查找，需要将intervals[][0]预先存放到一个新数组中，进行排序，再进行二分查找，由于排序会导致索引发生变化，因此需要另开map来将索引存起来

3. 代码

func findRightInterval(intervals [][]int) []int {
    var res []int
    array := make([]int, len(intervals))
    startMap := make(map[int]int, 0)

    for i := 0; i < len(intervals); i++ {
        array[i] = intervals[i][0]
        startMap[array[i]] = i
    }

    sort.Ints(array)

    for i := 0; i < len(intervals); i++ {
        var index int

        // 查找intervals[][0]中 >= intervals[i][1]的最小元素 
        start, ok := binarySearch(array, intervals[i][1])
        if !ok { // 如果没有查找到
            index = -1
        } else {
            index = startMap[start]
        }
        res = append(res, index)
    }
    return res
}

// 查找有序数组nums中， >= target的最小元素
func binarySearch(nums []int, target int) (int, bool) {
    left, right := 0, len(nums) - 1
    for left <= right {
        mid := left + (right - left) / 2
        if nums[mid] == target {
            return nums[mid], true
        } else if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    if left >= len(nums) {
        return -1, false
    }
    return nums[left], true
}