寻找右区间

题目链接

寻找右区间

题目描述

注意点

• -10^6 <= starti <= endi <= 10^6
• 每个间隔的起点都 不相同
• 如果某个区间 i 不存在对应的 右侧区间 ，则下标 i 处的值设为 -1

解答思路

• 因为本题需要找到每个interval大于interval对应end的最小start值，所以首先想到将start进行排序，又因为输出结果与原区间的顺序相同，所以使用一个新的数组leftIdxArr存储start及其在原数组对应的下标，随后对leftIdxArr进行排序
• 排序后遍历leftIdxArr，根据leftIdxArr[i][1]可以取得其在intervals的下标idx，也就能取到对应的end（intervals[idx][1]），然后对leftIdxArr二分查找大于end的最小start即可

代码

class Solution {
    public int[] findRightInterval(int[][] intervals) {
        int n = intervals.length;
        int[] res = new int[n];
        int[][] leftIdxArr = new int[n][2];
        for (int i = 0; i < n; i++) {
            leftIdxArr[i][0] = intervals[i][0];
            leftIdxArr[i][1] = i;
        }
        // 左区间从小到大进行排序
        Arrays.sort(leftIdxArr, new Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                return a[0] - b[0];
            }
        });
        for (int i = 0; i < n; i++) {
            int idx = leftIdxArr[i][1];
            int rightVal = intervals[idx][1];
            if (rightVal > leftIdxArr[n - 1][0]) {
                res[idx] = -1;
                continue;
            }
            // 二分查找找到最小“右”起点的下标
            res[idx] = binarySearch(leftIdxArr, rightVal, i, n - 1);
        }
        return res;
    }

    public int binarySearch(int[][] leftIdxArr, int rightVal, int left, int right) {
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (rightVal > leftIdxArr[mid][0]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return leftIdxArr[left][1];
    }
}

关键点

• 对左区间进行排序
• 二分查找的思想

原文地址：https://blog.csdn.net/weixin_51628158/article/details/142527745

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！