資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究在 C++ 中查詢包含恰好一個給定 N 個整數的最大區間
假設我們有一個包含 N 個不同整數的陣列。我們必須找到區間 [L, R] 中的最大元素，使得該區間恰好包含給定的 N 個整數中的一個，並且 1 <= L <= R <= 105。
因此，如果陣列類似於 Arr = [5, 10, 200]，則輸出為 99990。所以所有可能的區間是 [1, 9]、[6, 199] 和 [11, 100000]。最後一個區間包含最大整數，例如 99990
這個想法很簡單。我們將固定我們希望區間包含的元素。現在，我們將看看如何將我們的區間向左和向右擴充套件，而不會與其他元素重疊。所以我們必須首先對陣列進行排序，然後對於一個固定的元素，我們使用前一個和下一個元素來確定結束位置。我們將處理一些特殊情況。所以當我們固定第一個和最後一個區間時。這樣，對於每個元素 i，我們找到區間的最大長度。
示例
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int maximumSize(vector<int>& vec, int n) {
vec.push_back(0);
vec.push_back(100001);
n += 2;
sort(vec.begin(), vec.end());
int max_value = 0;
for (int i = 1; i < n - 1; i++) {
int Left = vec[i - 1] + 1;
int Right = vec[i + 1] - 1;
int count = Right - Left + 1;
max_value = max(max_value, count);
}
return max_value;
}
int main() {
vector<int> v;
v.push_back(200);
v.push_back(10);
v.push_back(5);
int n = v.size();
cout << "Maximum Size is: " << maximumSize(v, n);
}輸出
Maximum Size is: 99990
更新於: 2019-12-18
141 次瀏覽
廣告