ค้นหาองค์ประกอบที่เล็กที่สุดลำดับที่ k ในช่วง n ที่กำหนดใน C++

ในปัญหานี้ เราได้รับ n ช่วงและจำนวนเต็ม k งานของเราคือ ค้นหาองค์ประกอบที่เล็กที่สุดลำดับที่ k ในช่วง n ที่กำหนด

เราต้องหาองค์ประกอบที่เล็กที่สุดลำดับที่ k จากอาร์เรย์ที่สร้างขึ้นหลังจากรวมช่วงต่างๆ เข้าด้วยกัน

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

ป้อนข้อมูล: ช่วง ={{2, 5}, {7, 9}, {12, 15}}, k =9

ผลลัพธ์: 13

คำอธิบาย:

อาร์เรย์ที่สร้างคือ {2, 3, 4, 5, 7, 8, 9, 12, 13, 14, 15}

องค์ประกอบที่เล็กที่สุดคือ 13

แนวทางแก้ไข:

วิธีแก้ปัญหาอย่างง่ายคือการสร้างอาร์เรย์จากทุกช่วง และเมื่อสร้างจากช่วง อาร์เรย์จะเรียงลำดับจากน้อยไปมากด้วย ดังนั้นเราจึงต้องหาค่า kth ของอาร์เรย์

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

ตัวอย่าง

#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;
}

ผลลัพธ์

9th smallest element of the ranged array is 13