Tìm phần tử thứ k trong dãy từ N khoảng cho trước C++

Cho N khoảng [L, R] và số k. Nhiệm vụ: tìm phần tử thứ k trong dãy số tạo ra từ các khoảng.

Ví dụ minh họa

Input: ranges[][] = {{1, 3}, {5, 7}}, k = 4 Output: 5

Dãy: {1, 2, 3, 5, 6, 7}, phần tử thứ 4 là 5.

Phương pháp 1: Tạo mảng đầy đủ (O(total phần tử))

Duyệt tất cả khoảng, thêm vào mảng, trả về chỉ số k-1. Gây lỗi bộ nhớ nếu khoảng lớn.

Phương pháp 2: Tìm kiếm nhị phân + mảng đếm (O(log N))

Tạo mảng count[i] = số phần tử đến khoảng i. Tìm khoảng chứa phần tử thứ k bằng binary search. Tính chính xác giá trị trong khoảng đó.

Ví dụ chương trình (Phương pháp 2)

#include <iostream> 
using namespace std; 

int findKthSmallestEleSeries(int n, int k, int range[][2]){
    int count[n + 1];
    count[0] = 0;
    for (int i = 0; i < n; i++)
        count[i + 1] = count[i] + (range[i][1] - range[i][0]) + 1;
    
    int index = -1, mid;
    int start = 1, end = n;
    while (start <= end) {
        mid = (start + end) / 2;
        if (count[mid] > k) { index = mid; end = mid - 1; }
        else if (count[mid] < k) start = mid + 1;
        else { index = mid; break; }
    }
    start = range[index - 1][0];
    end = range[index - 1][1];
    int indexK = k - count[index - 1];
    while (start <= end) {
        mid = (start + end) / 2;
        if ((mid - range[index - 1][0]) + 1 == indexK) return mid;
        else if ((mid - range[index - 1][0]) + 1 > indexK) end = mid - 1;
        else start = mid + 1;
    }
    return -1;
}

int main(){
    int range[][2] = {{1, 3}, {5, 8}};
    int n = 2, k = 4;
    cout << k << "-th phần tử: " << findKthSmallestEleSeries(n, k, range);
    return 0;
}

Kết quả

4-th phần tử: 5