資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告