数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究在C++中查找右侧区间
假设我们有一组区间，对于每个区间 i，检查是否存在一个区间 j，其起始点大于或等于区间 i 的终点，这可以称为 j 在 i 的“右侧”。对于任何区间 i，我们必须存储区间 j 的最小索引，这表示区间 j 具有构建区间 i 的“右侧”关系的最小起始点。当区间 j 不存在时，则为区间 i 存储 -1。最后，我们需要将每个区间的存储值作为数组输出。因此，如果输入类似于 [[3,4], [2,3], [1,2]]，则输出将为 [-1, 0, 1]，因为 [3, 4] 没有这样的右侧区间；对于区间 [2,3]，区间 [3,4] 具有最小“右侧”起始点；对于 [1,2]，区间 [2,3] 具有最小“右侧”起始点。
为了解决这个问题，我们将遵循以下步骤：
n := 区间数组的大小，创建一个大小为 n 的数组 ret，并使用 -1 填充它，创建一个名为 m 的映射
对于 i 从 0 到区间大小
如果 intervals[i, 0] 在 m 中，则跳到下一个区间
m[intervals[i, 0]] := i + 1
对于 i 从 n – 1 到 i >= 0
it := 指向具有最小键但不大于 intervals[i, 1] 的键值对
如果 it 的值为 0，则进行下一次迭代
ret[i] := it 的值 – 1
返回 ret
示例 (C++)
让我们看看下面的实现，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> findRightInterval(vector<vector<int>>& intervals) {
int n = intervals.size();
vector <int> ret(n, -1);
map <int, int< m;
for(int i = 0; i < intervals.size(); i++){
if(m.count(intervals[i][0])) continue;
m[intervals[i][0]] = i + 1;
}
for(int i = n - 1; i >= 0; i--){
map <int, int> :: iterator it = m.lower_bound(intervals[i][1]);
if(it->second == 0) continue;
ret[i] = it->second - 1;
}
return ret;
}
};
main(){
vector<vector<int>> v = {{3,4},{2,3},{1,2}};
Solution ob;
print_vector(ob.findRightInterval(v));
}输入
[[3,4],[2,3],[1,2]]
输出
[-1,0,1]
更新于：2020年4月29日
324 次浏览
广告