इस समस्या में, हमें अंतराल L - R के बीच पूर्णांक मानों की N रेंज एक मैट्रिक्स range[N][2] के रूप में और एक पूर्णांक मान k दिया गया है। हमारा कार्य दिए गए N रेंज से उत्पन्न श्रृंखला में k-वां तत्व ज्ञात करना है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट : ranges[][] = {{1, 3}, {5, 7}}, k = 4 आउटपुट : 5 व्याख्या −
श्रृंखला है {1, 2, 3, 5, 6, 7} 4वां तत्व 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<<"-वां तत्व रेंज से उत्पन्न श्रृंखला का है "<< findKthSmallestEleSeries(n, k, range); return 0; } आउटपुट
4-वां तत्व रेंज से उत्पन्न श्रृंखला का है 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<<"-वां तत्व रेंज से उत्पन्न श्रृंखला का है "<< findKthSmallestEleSeries(n, k, range); return 0; } आउटपुट
4-वां तत्व रेंज से उत्पन्न श्रृंखला का है 5
