इस समस्या में, हमें अंतराल L - R के बीच एक मैट्रिक्स श्रेणी [N] [2] और एक पूर्णांक मान k के रूप में पूर्णांक मानों की एक N श्रेणी दी गई है। हमारा काम है दिए गए N श्रेणियों द्वारा उत्पन्न श्रृंखला में kth तत्व ढूंढना ।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
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
यह तरीका अच्छा है लेकिन अगर रेंज बहुत बड़ी हैं तो इससे मेमोरी की समस्या हो सकती है। इसलिए, हमें एक बेहतर दृष्टिकोण प्राप्त करने की आवश्यकता है जो सरणी के सभी तत्वों को संग्रहीत करता है।
एक और तरीका
समस्या को हल करने का एक अन्य तरीका द्विआधारी खोज और काउंटर सरणी का उपयोग करना है। काउंटर सरणी दी गई सीमा तक पूर्णांकों की संख्या को संग्रहीत करेगी, गिनती [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