Đếm số khoảng chứa giá trị cho trước trong C++

Cho một mảng 2D arr[][] chứa các khoảng và một số value. Mục tiêu là tìm số lượng khoảng trong arr mà value nằm trong đó. 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

Số lượng khoảng chứa giá trị cho trước là: 3

Giải thích

Giá trị 16 nằm giữa 1-20, 12-25 và 15-18

Đầu vào

arr[4][2] = {{ 1, 20 }, { 20,30 }, { 30, 40 }, { 40, 50 }} value=60

Đầu ra

Số lượng khoảng chứa giá trị cho trước là: 0

Giải thích

Giá trị 60 lớn hơn tất cả các phạm vi tối đa của các khoảng trong arr[][].

Phương pháp sử dụng

Trong phương pháp này, chúng ta sẽ tạo một mảng tần suất arr_2[] cho tất cả các số trong các phạm vi có trong arr. Với mỗi khoảng arr[i][0] và arr[i][1], tần suất sẽ được tăng trong arr_2[ arr[i][0 hoặc 1] ]. Cuối cùng, chúng ta sẽ cập nhật mảng tần suất 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 suất sẽ được cộng thêm. Theo cách này, chúng ta sẽ lấy được arr_2[value] là tất cả các khoảng mà value nằm trong đó.

Nhận mảng nguyên arr[][] chứa các khoảng.
Nhận giá trị nguyên value làm đầu vào.
Hàm intervals_values(int arr[][2], int size, int value) nhận arr và value và trả về số lượng khoảng mà giá trị cho trước nằm trong đó.
Tạo mảng tần suất arr_2[].
Khởi tạo low và highest là INT_MAX và INT_MIN.
Duyệt arr[][] bằng vòng lặp for từ i=0 đến i<size.
Lấy temp là giới hạn trái của khoảng và tăng tần suất của nó trong arr_2[temp].
Lấy temp_2 là giới hạn phải của khoảng và giảm tần suất của nó trong arr_2[temp_2 + 1].
Nếu temp < low thì gán low = temp và nếu temp_2 > highest thì gán highest = temp_2.
Duyệt mảng tần suất 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] làm kết quả.

Ví dụ mã

#include <bits/stdc++.h> 
using namespace std; 
#define max 1000 

int intervals_values(int arr[][2], int size, int value) {
    int arr_2[max] = {0};
    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 + 1; 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 << "Số lượng khoảng chứa giá trị cho trước là: " << intervals_values(arr, size, value);
    return 0;
}

Đầu ra

Nếu chạy mã trên, sẽ tạo ra đầu ra sau:

Số lượng khoảng chứa giá trị cho trước là: 2