给你一个区间数组 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 * 104intervals[i].length == 2
-106 <= starti <= endi <= 106每个间隔的起点都 不相同
解题思路
区间比较:首先想到的肯定是先排序,然后根据排序取值
所以排序的规则:我们需求是:拿到一个区间后,取这个区间的第二个值,然后去和其他区间的第一个值来比较,所以按照第一个值来排序
遍历源数组,拿每一个区间 interval
,使用二分法,找到比 interval[1]
大的最小值找到后,我们需要确定这个区间在原来数组中位置,那么我们需要事先用哈希存储一下位置信息
代码
// 436. 寻找有区间
func findRightInterval(_ intervals: [[Int]]) -> [Int] {
// 哈希记录每个区间的原来位置
var map = [[Int]: Int]()
for (index, value) in intervals.enumerated() {
map[value] = index
}
// 根据第一个值来排序
let sortIntervals = intervals.sorted { interval1, interval2 in
return interval1[0] < interval2[0]
}
// 结果集
var result = [Int](repeating: -1, count: intervals.count)
// 二分法查找比它大的最小值
for (index, interval) in intervals.enumerated() {
var left = 0, right = sortIntervals.count - 1
while left < right {
let mid = left + ((right - left) >> 1)
if sortIntervals[mid][0] >= interval[1] {
right = mid
} else {
left = mid + 1
}
}
if left == sortIntervals.count - 1, sortIntervals[left][0] < interval[1] {
result[index] = -1
} else {
// 找到,去哈希中取位置
result[index] = map[sortIntervals[left]]!
}
}
return result
}
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)