ในปัญหานี้ เราได้รับช่วง N ของค่าจำนวนเต็มระหว่างช่วง L - R เป็นช่วงเมทริกซ์[N][2] และค่าจำนวนเต็ม k งานของเราคือ ค้นหาองค์ประกอบที่ k ในอนุกรมที่สร้างโดยช่วง N ที่กำหนด .
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
Input : ranges[][] = {{1, 3}, {5, 7}}, k = 4
Output : 5 คำอธิบาย −
The series is {1, 2, 3, 5, 6, 7}
The 4th element is 5. แนวทางการแก้ปัญหา
วิธีแก้ปัญหาอย่างง่ายคือการสร้างชุดของจำนวนเต็มสำหรับช่วงที่กำหนด จากนั้นค้นหาองค์ประกอบที่ดัชนี k ของอาร์เรย์
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#include <iostream>
using namespace std;
int findKthSmallestEleSeries(int n, int k, int range[][2]){
int rangeVal[10000];
int rangeSize = 0;
for(int i = 0; i < n; i++){
for(int j = range[i][0]; j <= range[i][1]; j++){
rangeVal[rangeSize] = j;
rangeSize++;
}
}
return rangeVal[k-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<<k<<"-th element of the series generated by ranges is "<<
findKthSmallestEleSeries(n, k, range);
return 0;
} ผลลัพธ์
4-th element of the series generated by ranges is 5
วิธีนี้เป็นวิธีที่ดีแต่อาจนำไปสู่ปัญหาหน่วยความจำได้หากช่วงมีขนาดใหญ่เกินไป ดังนั้นเราจึงต้องหาแนวทางที่ดีกว่าในการจัดเก็บองค์ประกอบทั้งหมดของอาร์เรย์
แนวทางอื่น
อีกวิธีในการแก้ปัญหาคือการใช้การค้นหาแบบไบนารีและอาร์เรย์ตัวนับ อาร์เรย์ตัวนับจะเก็บการนับจำนวนเต็มจนถึงช่วงที่กำหนด count[i] =จำนวนอักขระจนถึงช่วงที่ i
จากนั้นสำหรับ k เราจะหาช่วงหมายเลข i ซึ่งมีค่าน้อยที่สุดที่ k อยู่
แล้วเราจะหาค่าในช่วงนี้
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#include <iostream>
using namespace std;
int findKthSmallestEleSeries(int n, int k, int range[][2]){
int start = 1;
int end = n;
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;
int mid;
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 L[] = { 1, 5 };
int R[] = { 3, 8 };
int range[][2] = {{1, 3}, {5, 8}};
int n = sizeof(L) / sizeof(int);
int k = 4;
cout<<k<<"-th element of the series generated by ranges is "<<
findKthSmallestEleSeries(n, k, range);
return 0;
} ผลลัพธ์
4-th element of the series generated by ranges is 5
