题目地址:https://leetcode-cn.com/problems/find-right-interval/
给定一组区间,对于每一个区间 i,检查是否存在一个区间 j,它的起始点大于或等于区间 i 的终点,这可以称为 j 在 i 的“右侧”。
对于任何区间,你需要存储的满足条件的区间 j 的最小索引,这意味着区间 j 有最小的起始点可以使其成为“右侧”区间。如果区间 j 不存在,则将区间 i 存储为 -1。最后,你需要输出一个值为存储的区间值的数组。
注意:
你可以假设区间的终点总是大于它的起始点。
你可以假定这些区间都不具有相同的起始点。
示例 1:输入: [ [1,2] ]
输出: [-1]解释:集合中只有一个区间,所以输出-1。
示例 2:输入: [ [3,4], [2,3], [1,2] ]
输出: [-1, 0, 1]解释:对于[3,4],没有满足条件的“右侧”区间。
对于[2,3],区间[3,4]具有最小的“右”起点;
对于[1,2],区间[2,3]具有最小的“右”起点。
示例 3:输入: [ [1,4], [2,3], [3,4] ]
输出: [-1, 2, -1]解释:对于区间[1,4]和[3,4],没有满足条件的“右侧”区间。
对于[2,3],区间[3,4]有最小的“右”起点。
编程思路
此题可以硬解,先遍历所有区间尾,对于每尾再遍历一次所有的头,找出最小的即可。我选择麻烦一点,先对区间们依据区间首进行升序排序,然后再从头依次遍历区间尾,从该区间起向后查找。
-
二路归并排序
对区间的排序采用二路归并排序。归并排序使用分治思想,稳定,最好最坏平均时间复杂度都是O(nlog2n)。同样时间复杂度的排序中,快速排序不稳定,且当元素顺序和逆序时出现最坏情况O(n²),堆排序不稳定。归并排序消耗内存O(n)。
归并排序
下面是归并排序过程,核心就是比较左右指针内容的大小,画画板做的gif将就着看吧。
归并过程.gif -
折半查找
区间排序完成后,起点已经是升序,接下来只需对所有区间尾依次进行处理,在其他区间找出比其大得最少或者值相等的一个起点。我们只需要对其后的区间的头进行查找即可,由于区间起点升序,因此采用二分查找法快些。
例如对{2,5,7,17,18,56}进行折半查找,查找的路径相当于一个平衡的二叉排序树,查找成功也好,失败也好,最多也就比较树高次,是O(log2n)数量级。
image.png
代码
class Solution {
public:
vector<int> findRightInterval(vector<vector<int>>& intervals) {
int size=intervals.size();
vector<int> indexes;
vector<int> results;
for(int k=0;k<size;k++){
indexes.push_back(k);
results.push_back(k);
}
mergeSort(intervals,indexes,0,size-1);
//binary search
for(int k=0;k<size;k++){
int target=intervals[indexes[k]][1];
int low=k+1,high=size-1,mid;
int result=-1;
while(low<=high){
mid=(low+high)/2;
if(target==intervals[indexes[mid]][0]){//found
result=indexes[mid];
break;
}
else if(target<intervals[indexes[mid]][0]){
result=indexes[mid];
high=mid-1;
}
else if(target>intervals[indexes[mid]][0]){
low=mid+1;
}
}
results[indexes[k]]=result;
}
return results;
}
/*
custom merge sort,modified units' index will be stored in inputIndex
*/
void mergeSort(vector<vector<int>>& inputVec,vector<int> &inputIndex,int low,int high){
if(low<high){
int mid=(low+high)/2;
mergeSort(inputVec,inputIndex,low,mid);//left part sort
mergeSort(inputVec,inputIndex,mid+1,high);//right part sort
innerMerge(inputVec,inputIndex,low,mid,high);//both left and right already sorted,now merge them into one piece.
}
}
/*
merge low ~ mid and mid+1 ~ high into one piece
*/
void innerMerge(vector<vector<int>>& inputVec,vector<int> &inputIndex,int low,int mid,int high){
int i,j,k;
auto indexCopy=inputIndex;
printf("%d ",low);
for(i=low,j=mid+1,k=low;i<=mid&&j<=high;k++){//caution:k=low
if(inputVec[indexCopy[i]][0]<inputVec[indexCopy[j]][0]){//left<right
inputIndex[k]=indexCopy[i++];
}
else {//left>right
inputIndex[k]=indexCopy[j++];
}
}
while(i<=mid){
inputIndex[k++]=indexCopy[i++];
}
while(j<=high){
inputIndex[k++]=indexCopy[j++];
}
}
};
性能:
都不好意思贴出来了
image.png
网友评论