数据结构
网络
关系数据库管理系统
操作系统
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 次浏览
广告