Tìm phần tử nhỏ nhất thứ k trong n dãy đã cho trong C ++

Trong bài toán này, chúng ta có n dãy và một số nguyên k. Nhiệm vụ của chúng ta là tìm phần tử nhỏ nhất thứ k trong n dãy đã cho.

Chúng ta cần tìm phần tử nhỏ nhất thứ k từ mảng được tạo sau khi kết hợp các phạm vi.

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

Đầu vào: phạm vi ={{2, 5}, {7, 9}, {12, 15}}, k =9

Đầu ra: 13

Giải thích:

Mảng được tạo là {2, 3, 4, 5, 7, 8, 9, 12, 13, 14, 15}

Các phần tử nhỏ nhất là 13

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ảng từ tất cả các phạm vi và vì nó được tạo từ phạm vi nên nó cũng được sắp xếp theo thứ tự tăng dần. Do đó, chúng ta chỉ cần tìm giá trị thứ k của mảng.

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

Ví dụ

#include <iostream>
using namespace std;

int main(){
   
   int arr[][2] = {{2, 5}, {7, 9}, {12, 15}};
   int n = sizeof(arr)/sizeof(arr[0]);
   int k = 9;

   int rangeArr[1000];
   int size = 0;
   for(int i = 0; i < n; i++)
      for(int j = arr[i][0]; j <= arr[i][1]; j++) {
         rangeArr[size] = j;  
         size++;
      }
   if(k < size)
      cout<<k<<"th smallest element of the ranged array is "<<rangeArr[k]<<endl;
   else
      cout<<"invalid Index";
   return 0;
}

Đầu ra

9th smallest element of the ranged array is 13