作者：哇哈哈啦啦啦啦_729 | 来源：互联网 | 2024-11-23 14:17
本题提供了一个区间数组intervals，其中每个区间intervals[i]包含两个整数[starti,endi]，并且所有starti值各不相同。任务是找到每个区间的右侧区间，即存在一个区间j满足startj>=endi并且startj是尽可能小的。返回一个数组，该数组包含每个区间右侧区间的索引；如果没有合适的右侧区间，则返回-1。
题目描述
给定一个区间数组 intervals，其中每个区间 intervals[i] = [starti, endi]，且每个 starti 值都是唯一的。定义区间 i 的右侧区间为另一个区间 j，需满足 startj >= endi，同时 startj 应尽可能小。返回一个数组，该数组包含每个区间 i 的右侧区间在 intervals 中的索引。若某区间无对应的右侧区间，则该位置应设为 -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 * 10^4
intervals[i].length == 2
-10^6 <= starti <= endi <= 10^6
每个区间的起点都各不相同。
解题思路
解决此类寻找首个大于或等于特定值的问题时，二分查找是一种高效的方法。由于问题要求的是找到值而非具体数值，我们需要创建一个新的数组来存储所有区间的起点及其原始索引，然后对这个新数组进行排序。之后，通过二分查找来定位每个区间右侧区间的索引。
解决方案代码
Java 实现
class Solution {
public int[] findRightInterval(int[][] intervals) {
int n = intervals.length;
int[] result = new int[n];
int[][] starts = new int[n][2];
for (int i = 0; i starts[i][0] = intervals[i][0];
starts[i][1] = i;
}
Arrays.sort(starts, (a, b) -> a[0] - b[0]);
for (int i = 0; i result[i] = binarySearch(starts, intervals[i][1]);
}
return result;
}
private int binarySearch(int[][] starts, int target) {
int left = 0, right = starts.length - 1, answer = -1;
while (left <= right) {
int mid = (left + right) / 2;
if (starts[mid][0] >= target) {
answer = starts[mid][1];
right = mid - 1;
} else {
left = mid + 1;
}
}
return answer;
}
}
在编程和算法设计中，保持谦逊的态度，勇于面对挑战。
京公网安备 11010802041100号