ในปัญหานี้ เราได้รับช่วง 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