LeetCode_二分搜索_中等_436.寻找右区间

╰半夏微凉° 2023-10-06 23:50 8阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给你一个区间数组 intervals ，其中 intervals\[i\] = \[starti, endi\] ，且每个 starti 都不同 。

区间 i 的右侧区间可以记作区间 j，并满足 startj >= endi，且 startj 最小化。

返回一个由每个区间 i 的右侧区间在 intervals 中对应下标组成的数组。如果某个区间 i 不存在对应的右侧区间，则下标 i 处的值设为 -1。

**示例 1：**  
输入：intervals = \[\[1,2\]\]  
输出：\[-1\]  
解释：集合中只有一个区间，所以输出 -1。

**示例 2：**  
输入：intervals = \[\[3,4\],\[2,3\],\[1,2\]\]  
输出：\[-1,0,1\]  
解释：对于 \[3,4\] ，没有满足条件的“右侧”区间。  
对于 \[2,3\] ，区间 \[3,4\] 具有最小的“右”起点;  
对于 \[1,2\] ，区间 \[2,3\] 具有最小的“右”起点。

**示例 3：**  
输入：intervals = \[\[1,4\],\[2,3\],\[3,4\]\]  
输出：\[-1,2,-1\]  
解释：对于区间 \[1,4\] 和 \[3,4\] ，没有满足条件的“右侧”区间。  
对于 \[2,3\] ，区间 \[3,4\] 有最小的“右”起点。

**提示：**  
1 <= intervals.length <= 2 \* 104  
intervals\[i\].length == 2  
\-106 <= starti <= endi <= 106  
每个间隔的起点都不相同

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/find-right-interval

## 2.思路 ##

（1）暴力穷举法  
暴力穷举法比较容易想到，其具体步骤如下：  
① 记 n = intervals.length 是区间个数，并定义长度为 n 的结果数组 res；  
② 开始遍历每个区间：  
1）第一层 for 循环：在针对每个区间 intervals\[i\] 时，分别用 minStart 和 minIndex 记录该区间对应的最小 startj 以及对应的下标 j，初始值分别为 Integer.MAX\_VALUE 和 -1；  
2）第二层 for 循环：从第一个区间 intervals\[j\] 开始判断，如果 startj ≥ endi 并且 minStart ≥ startj，那么就更新 minStart 和 minIndex；  
3）第二层 for 循环结束后，直接用 res 来记录当前区间的右侧区间在 intervals 中对应下标组成的数组，即 res\[i\] = minIndex；  
③ 所有区间遍历结束后，直接返回 res 即可。

（2）排序 & 二分搜索  
我们可以**在方法 1 的基础上进行时间复杂度的优化**，在方法 1 的第 2 层 for 循环中，为了获得 minStart 和 minIndex，需要遍历所有的区间，显然其时间复杂度较高，所以优化的思路就是：  
① 定义如下的二维数组 cloneIntervals，用于**保存每个区间的起点以及每个区间在 intervals 中的下标**；

// cloneIntervals 保存每个区间的起点以及每个区间在 intervals 中的下标
    int[][] cloneIntervals = new int[intervals.length][2];

② 然后再将 cloneIntervals **按照区间的起点进行升序排序**，这样就可以直接使用二分搜索算法来查找即可。

> 需要注意的是，本方法虽然降低了时间复杂度，但是由于需要额外定义数组 cloneIntervals，所以又提高了空间复杂度，即优化中常见的**空间换时间**。除此之外，由于题目要求的答案与 intervals 中区间的顺序有关，所以不能直接对 intervals 进行排序。

## 3.代码实现（Java） ##

//思路1————暴力穷举法
    class Solution {
        
        public int[] findRightInterval(int[][] intervals) {
        
            //区间个数
            int n = intervals.length;
            int[] res = new int[n];
            for (int i = 0; i < n; i++) {
        
                int minStart = Integer.MAX_VALUE;
                int minIndex = -1;
                for (int j = 0; j < n; j++) {
        
                    if (intervals[j][0] >= intervals[i][1]) {
        
                        if (minStart >= intervals[j][0]) {
        
                            minStart = intervals[j][0];
                            minIndex = j;
                        }    
                    }
                }
                res[i] = minIndex;
            }
            return res;
        }
    }

//思路2————排序 & 二分搜索
    class Solution {
        
        public static int[] findRightInterval(int[][] intervals) {
        
            //区间个数
            int n = intervals.length;
            int[] res = new int[n];
            // cloneIntervals 保存每个区间的起点以及每个区间在 intervals 中的下标
            int[][] cloneIntervals = new int[n][2];
            for (int i = 0; i < n; i++) {
        
                cloneIntervals[i] = new int[]{
        intervals[i][0], i};
            }
            //将 cloneIntervals 按照区间的起点进行升序排序(本题中每个间隔的起点都不相同)
            Arrays.sort(cloneIntervals, (interval1, interval2) -> interval1[0] - interval2[0]);
            for (int i = 0; i < n; i++) {
        
            	//从 cloneIntervals 找出大于等于 intervals[i][1] 的最小区间起点(即最左端点)
                int left = 0;
                int right = n - 1;
                while (left <= right) {
        
                    int mid = left + (right - left) / 2;
                    if (cloneIntervals[mid][0] < intervals[i][1]) {
        
                        left = mid + 1;
                    } else {
        
                        right = mid - 1;
                    }
                }
                // left >= n 说明未能找到大于等于 intervals[i][1] 的起点
                res[i] = (left >= n) ? -1 : cloneIntervals[left][1];
            }
            return res;
        }
    }