力扣解法汇总436-寻找右区间
目录链接:
力扣编程题-解法汇总_分享+记录-CSDN博客
GitHub同步刷题项目:
https://github.com/September26/java-algorithms
原题链接:力扣
描述:
给你一个区间数组 intervals ,其中 intervals[i] = [starti, endi] ,且每个 starti 都 不同 。
区间 i 的 右侧区间 可以记作区间 j ,并满足 startj >= endi ,且 startj 最小化 。
返回一个由每个区间 i 的 右侧区间 的最小起始位置组成的数组。如果某个区间 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
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题思路:
* 解题思路: * 这题涉及到两次排序,为了方便理解,我们构建Model来存储这关系。Model记录start,end,和在intervals的位置index。 * 然后分别以start和end排序,生成两个集合startList和endList。 * 然后遍历endList,同时也从startList中取值。如果startList中的start大于endlist中的end。则代表符合,则记录其index。 * 如果找不到,则记录-1
代码:
public class Solution436 {
public int[] findRightInterval(int[][] intervals) {
Map<Integer, Model> map = new HashMap<>();
for (int i = 0; i < intervals.length; i++) {
Model model = new Model(intervals[i][0], intervals[i][1], i);
map.put(i, model);
}
List<Model> startList = new ArrayList<>(map.values());
startList.sort(new Comparator<Model>() {
@Override
public int compare(Model o1, Model o2) {
return o1.start - o2.start;
}
});
List<Model> endList = new ArrayList<>(map.values());
endList.sort(new Comparator<Model>() {
@Override
public int compare(Model o1, Model o2) {
return o1.end - o2.end;
}
});
int[] result = new int[intervals.length];
int startIndex = 0;
for (Model endModel : endList) {
Model startModel = null;
while (startIndex < startList.size()) {
Model model = startList.get(startIndex);
if (model.start >= endModel.end) {
startModel = model;
break;
}
startIndex++;
}
if (startModel == null) {
result[endModel.index] = -1;
} else {
result[endModel.index] = startModel.index;
}
}
return result;
}
static class Model {
int start = 0;
int end = 0;
int index = 0;
Model(int start, int end, int index) {
this.start = start;
this.end = end;
this.index = index;
}
}
}
相关文章
- modbus系列文章—汇总
- Sql Server A表汇总到B表存储过程(直接赋参数用,源码)
- Python标准库中的列表(list、数组)操作汇总(大约25种操作),附示例代码
- 最全的Swift社交应用文本输入优化汇总
- 数据科学必备Pandas数据分组GroupBy方法汇总
- 剑指offer编程题解法汇总10-矩形覆盖
- 力扣解法汇总1662. 检查两个字符串数组是否相等
- 力扣解法汇总1750. 删除字符串两端相同字符后的最短长度
- 力扣解法汇总1475-商品折扣后的最终价格
- 力扣解法汇总745-前缀和后缀搜索
- 力扣解法汇总676-实现一个魔法字典
- 力扣解法汇总564-寻找最近的回文数
- 力扣解法汇总306-累加数
- 力扣解法汇总26-删除有序数组中的重复项
- JS面试题汇总(四)
- 【C语言】运算符与操作符的用法全面汇总(非常有用)
- 研究生数学建模历年题目汇总