AlgoPressAppearance
0436-寻找右区间
题目描述
https://leetcode.cn/problems/find-right-interval
给你一个区间数组 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 * 10^4
- intervals[i].length == 2
- -10^6 <= starti <= endi <= 10^6
- 每个间隔的起点都 不相同
思路：暴力法
因为我们要取得数组的索引，所以不能直接原地排序数组。
暴力搜索，对于每个数 intervals[i][1] 遍历 j 找出右区间, 即 intervals[j][0] >= 它。 这里需要注意的是，他需要找最小的那个右区间，而不是 索引 最小的那个，所以我们还需要记录一个差值，如果当前差值小于之前的差值我们才替换。
csharp
public class Solution {
public int[] FindRightInterval(int[][] intervals) {
//暴力搜索
int n = intervals.Length;
int[] result = new int[n];
for(int i=0; i<intervals.Length; i++){
int index = -1;
int sub = int.MaxValue; //差值
for(int j=0; j<intervals.Length; j++){
if(intervals[j][0] >= intervals[i][1]){
if(intervals[j][0] - intervals[i][1] < sub){
index = j;
sub = intervals[j][0] - intervals[i][1];
}
}
}
result[i] = index;
}
return result;
}
}
思路：二分查找
上述暴力法可以通过，但是时间复杂度是 O(n^2) 我们可以将区间起点记录到一个数组，然后将索引记录到新数组。
再 使用二分法查找对应的结果，满足条件时记录 索引值。
csharp
public class Solution {
public int[] FindRightInterval(int[][] intervals) {
//二分查找
int n = intervals.Length;
int[] result = new int[n];
int[][] ints = new int[n][];
for(int i=0; i<n; i++){
ints[i] = new int[]{intervals[i][0],i}; //记录左边界,记录索引
}
//排序左边界
Array.Sort(ints,(a,b)=>{
return a[0].CompareTo(b[0]);
});
//输出排序数组
// for(int i=0; i<n; i++){
// Console.WriteLine("ints[{0}={1},{2}]",i,ints[i][0],ints[i][1]);
// }
//二分查找
for(int i=0; i<n; i++){
int left = 0;
int right = n-1;
int target = -1;
while(left <= right){
int mid = left + (right - left) / 2;
if(intervals[i][1] <= ints[mid][0]){
target = ints[mid][1];
right = mid - 1;
}
else{
left = mid + 1;
}
}
result[i] = target;
}
return result;
}
}
思路：双指针
将开始位置的数值和索引也加入数组，进行排序，这样就不用二分查找结束的位置。
csharp
public class Solution{
public int[] FindRightInterval(int[][] intervals){
int n = intervals.Length;
int[] result = new int[n];
int[][] startIntervals = new int[n][]; //开始位置集合
int[][] endIntervals = new int[n][]; //结束位置集合
for(int i=0; i<n; i++){
startIntervals[i] = new int[]{intervals[i][0],i};
endIntervals[i] = new int[]{intervals[i][1],i};
}
Array.Sort(startIntervals,(a,b)=>{return a[0].CompareTo(b[0]);});
Array.Sort(endIntervals,(a,b)=>{return a[0].CompareTo(b[0]);});
int j=0;
for(int i=0; i<n; i++){
while(j < n && startIntervals[j][0] < endIntervals[i][0]){
j++;
}
if(j < n){
result[endIntervals[i][1]] = startIntervals[j][1];
}
else{
result[endIntervals[i][1]] = -1;
}
}
return result;
}
}
复习: 20220712
csharp
public class Solution{
public int[] FindRightInterval(int[][] intervals){
int n = intervals.Length;
int[] result = new int[n];
int[][] startIntervals = new int[n][]; //开始位置集合
int[][] endIntervals = new int[n][]; //结束位置集合
//将开始节点和结束节点的索引都加入进去
for(int i=0; i<n; i++){
startIntervals[i] = new int[]{intervals[i][0],i};
endIntervals[i] = new int[]{intervals[i][1],i};
}
//按照开始节点排序
Array.Sort(startIntervals,(a,b)=>{return a[0].CompareTo(b[0]);});
//按照结束节点排序
Array.Sort(endIntervals,(a,b)=>{return a[0].CompareTo(b[0]);});
int j=0;
//遍历结束节点
for(int i=0; i<n; i++){
//因为是要考虑右区间，因为开始节点在我之前的都不做考虑
while(j < n && startIntervals[j][0] < endIntervals[i][0]){
j++;
}
//如果j还存在，j就是目前最小的那个右区间，取出他的索引，更新到 result 里面去
if(j < n){
result[endIntervals[i][1]] = startIntervals[j][1];
}
else{ //如果 j 不存在，则赋值为 -1
result[endIntervals[i][1]] = -1;
}
}
return result;
}
}