Tìm phần tử thứ k trong chuỗi được tạo bởi N dãy đã cho trong C ++

Trong bài toán này, chúng ta được cung cấp N dãy giá trị nguyên giữa các khoảng L - R dưới dạng một dãy ma trận [N] [2] và một giá trị nguyên k. Nhiệm vụ của chúng ta là tìm phần tử thứ k trong chuỗi được tạo bởi N dãy đã cho .

Hãy lấy một ví dụ để hiểu vấn đề,

 Đầu vào:dãy [] [] ={{1, 3}, {5, 7}}, k =4 Đầu ra:5 

Giải thích -

 Chuỗi là {1, 2, 3, 5, 6, 7} Phần tử thứ 4 là 5. 

Phương pháp tiếp cận giải pháp

Một giải pháp đơn giản cho vấn đề là tạo một chuỗi các số nguyên cho các phạm vi đã cho và sau đó tìm các phần tử ở chỉ số k của mảng của chúng.

Ví dụ

Chương trình minh họa hoạt động của giải pháp của chúng tôi

 #include  using namespace std; int findKthSmallestEleSeries (int n, int k, int range [] [2]) {int rangeVal [10000]; int rangeSize =0; for (int i =0; i  
 Đầu ra 
 Phần tử thứ 4 của chuỗi được tạo bởi các dải ô là 5 

Phương pháp này tốt nhưng có thể dẫn đến các vấn đề về bộ nhớ nếu phạm vi quá lớn. Do đó, chúng ta cần tìm ra một cách tiếp cận tốt hơn để lưu trữ tất cả các phần tử của mảng.

Một cách tiếp cận khác

Một cách tiếp cận khác để giải quyết vấn đề là sử dụng tìm kiếm nhị phân và mảng bộ đếm. Mảng bộ đếm sẽ lưu trữ số lượng các số nguyên cho đến phạm vi đã cho, count [i] =số ký tự cho đến phạm vi thứ i.

Sau đó với k, chúng ta sẽ tìm dãy số i, trong đó giá trị nhỏ nhất thứ k nằm trong đó.

Sau đó, chúng tôi sẽ tìm giá trị trong phạm vi này.

Ví dụ

Chương trình minh họa hoạt động của giải pháp của chúng tôi

 #include  using namespace std; int findKthSmallestEleSeries (int n, int k, int range [] [2]) {int start =1; int end =n; int count [n + 1]; đếm [0] =0; for (int i =0; i  k) {index =mid; end =mid - 1; } else if (count [mid]  indexK) end =mid - 1; else start =mid + 1; } return -1;} int main () {int L [] ={1, 5}; int R [] ={3, 8}; int range [] [2] ={{1, 3}, {5, 8}}; int n =sizeof (L) / sizeof (int); int k =4; cout < 
 Đầu ra 
 Phần tử thứ 4 của chuỗi được tạo bởi các dải ô là 5