Cho một mảng 2D arr [] [] chứa các khoảng và một số "giá trị". Mục đích là để tìm số khoảng có trong arr giữa giá trị đó nằm. Ví dụ các khoảng là [[1,5], [3,7]] và value =4 thì nó nằm trong cả hai khoảng này và số lượng sẽ là 2.
Ví dụ
Đầu vào
arr[4][2] = { { 1, 20 }, { 12, 25 }, { 32, 40 }, { 15, 18 } } value=16 Đầu ra
Count of number of intervals in which a given value lies are: 3
Giải thích
The value 16 lies between 1−20, 12−25 and 15−18
Đầu vào
arr[4][2] = {{ 1, 20 }, { 20,30 }, { 30, 40 }, { 40, 50 }} value=60 Đầu ra
Count of number of intervals in which a given value lies are: 0
Giải thích
The value 60 is larger than all maximum ranges of intervals present in arr[][].
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau -
Trong cách tiếp cận này, chúng tôi sẽ tạo một mảng tần số arr_2 [] cho tất cả các số của các phạm vi có trong arr. Vì vậy, đối với arr [i] [0] và arr [i] [1] của mỗi dải, tần số sẽ được tăng lên trong arr_2 [arr [i] [0 hoặc 1]]. Cuối cùng, chúng tôi sẽ cập nhật mảng tần số với arr_2 [i] =arr_2 [i] + arr_2 [i-1] vì các số nhỏ hơn i-1 cũng sẽ nhỏ hơn i nên tần số sẽ được thêm vào. Bằng cách này, chúng tôi sẽ nhận được arr_2 [giá trị] là tất cả các phạm vi có giá trị nằm trong đó.
-
Lấy một mảng số nguyên arr [] [] chứa các dải ô.
-
Lấy một giá trị số nguyên làm đầu vào.
-
Hàm khoảng_giá_trị (int arr [] [2], int size, int value) nhận arr và giá trị và trả về số lượng khoảng có một giá trị nhất định.
-
Lấy mảng tần số arr_2 [].
-
Lấy thấp và cao nhất là INT_MAX và INT_MIN.
-
Traverse arr [] [] sử dụng vòng lặp for từ i =0 đến i
-
Hãy tạm thời ở bên trái của phạm vi và tăng tần số của nó trong arr_2 [temp]
-
Lấy temp_2 ở bên phải của dải ô và tăng tần số của nó trong arr_2 [temp_2 + 1]
-
Nếu temp
cao nhất hãy đặt cao nhất là temp_2. -
Duyệt mảng tần số và cập nhật nó arr_2 [i] =arr_2 [i] + arr_2 [i + 1].
-
Cuối cùng, trả về arr_2 [value].
Ví dụ
#include<bits/stdc++.h>
using namespace std;
#define max 1000
int intervals_values(int arr[][2], int size, int value){
int arr_2[max];
int low = INT_MAX;
int highest = INT_MIN;
for(int i = 0; i < size; i++){
int temp = arr[i][0];
arr_2[temp] = arr_2[temp] + 1;
int temp_2 = arr[i][1];
arr_2[temp_2 + 1] = arr_2[temp_2 + 1] − 1;
if(temp < low){
low = temp;
}
if(temp_2 > highest){
highest = temp_2;
}
}
for (int i = low; i <= highest; i++){
arr_2[i] = arr_2[i] + arr_2[i − 1];
}
return arr_2[value];
}
int main(){
int arr[4][2] = { { 3, 20 }, { 2, 13 }, { 25, 30 }, { 15, 40 } };
int size = sizeof(arr) / sizeof(arr[0]);
int value = 28;
cout<<"Count the number of intervals in which a given value lies are:
"<<intervals_values(arr, size, value);
return 0;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Count the number of intervals in which a given value lies are: 18830628