Tìm khoảng lớn nhất chứa đúng một trong N số nguyên đã cho Trong C ++

Giả sử chúng ta có một mảng gồm N số nguyên riêng biệt. Chúng ta phải tìm phần tử lớn nhất trong một khoảng [L, R] sao cho khoảng đó chứa đúng một trong N số nguyên đã cho và 1 <=L <=R <=10 ⁵ .

Vì vậy, nếu mảng giống như Arr =[5, 10, 200], thì đầu ra là 99990. Vì vậy, tất cả các khoảng có thể là [1, 9], [6, 199] và [11, 100000]. Cái cuối cùng có các số nguyên tối đa như 99990

Ý tưởng là đơn giản. Chúng tôi sẽ sửa phần tử mà chúng tôi muốn khoảng thời gian của chúng tôi chứa. Bây giờ, chúng ta sẽ xem làm thế nào chúng ta có thể kéo dài khoảng thời gian của mình sang trái và phải mà không chồng chéo các yếu tố khác. Vì vậy, chúng ta phải sắp xếp mảng trước, sau đó đối với một phần tử cố định, chúng ta xác định phần cuối bằng cách sử dụng phần tử trước đó và tiếp theo. Chúng tôi sẽ xử lý các trường hợp góc. Vì vậy, khi chúng tôi đang sửa các khoảng đầu tiên và cuối cùng. Bằng cách này với mọi phần tử i, chúng tôi tìm được độ dài lớn nhất của khoảng.

Ví dụ

#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);
}

Đầu ra

Maximum Size is: 99990