समस्या
मान लीजिए, हमारे पास संख्याओं के सरणियों की एक क्रमबद्ध सरणी है (बढ़ते क्रम में क्रमबद्ध) इस तरह -
const arr = [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15] ];
हमें एक जावास्क्रिप्ट फ़ंक्शन लिखना आवश्यक है जो पहले तर्क के रूप में एक ऐसी सरणी और दूसरे तर्क के रूप में एक पूर्णांक, संख्या लेता है।
हमारा कार्य सरणी गिरफ्तारी में मौजूद संख्या के सबसे छोटे तत्व को वापस करने वाला है।
उदाहरण के लिए, यदि फ़ंक्शन का इनपुट है -
const arr = [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15] ]; const num = 5;
आउटपुट
तब आउटपुट होना चाहिए -
const output = 11;
आउटपुट स्पष्टीकरण:
11 मैट्रिक्स में पांचवां सबसे छोटा तत्व है।
उदाहरण
इसके लिए कोड होगा -
const arr = [
[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]
];
const num = 5;
const kthSmallest = (arr = [], num = 1) => {
let low = arr[0][0]
let high = arr[arr.length-1][arr[0].length-1] + 1;
while (low < high) {
let mid = low + Math.floor((high-low)/2);
let count = 0;
for (let i = 0;i<arr.length;i++) {
for (let j=0;j<arr.length;j++) {
if (arr[i][j] <= mid) count++;
else break;
}
}
if (count < num) low = mid+1;
else high = mid;
}
return low
};
console.log(kthSmallest(arr, num)); कोड स्पष्टीकरण:
यहाँ विचार है -
जब हमारे पास नियमित रूप से क्रमबद्ध 2d सरणी होती है, तो हम अपने लक्ष्य को खोजने के लिए कई तरह के इंडेक्स का उपयोग करते हैं, उदाहरण के लिए,
low = 0, high = length-1, mid = (low+high)/2
यदि लक्ष्य सूचकांक मध्य की संख्या से बड़ा है, तो हम दाहिने हिस्से को खोजते हैं, यदि यह छोटा है, तो हम बाईं ओर खोजते हैं।
हालाँकि, इस 2d arr सॉर्ट किए गए सरणी में, ऐसा मध्य अनुक्रमणिका खोजना असंभव है। यहाँ अंतर्ज्ञान हमारे k के विरुद्ध परीक्षण करने के लिए संख्याओं की एक श्रृंखला का उपयोग करना है। हम जानते हैं कि पहली संख्या सबसे छोटी है और अंतिम संख्या सबसे बड़ी है, इसका मतलब है कि हमारा लक्ष्य संख्या बीच में कुछ होना चाहिए। हम उन दो संख्याओं को अपने निम्न और उच्च के रूप में उपयोग कर सकते हैं, और हमारे मध्य को बीच की संख्या के रूप में सेट कर सकते हैं, और जांच सकते हैं कि गिरफ्तारी में कितनी संख्याएं उस संख्या से छोटी हैं और तदनुसार निम्न और उच्च समायोजित करें।
जब हमें ठीक-ठीक k अंक मिलते हैं, तो हम जानते हैं कि हमें अपना उत्तर मिल गया है। यहां बेहद मुश्किल हिस्सा यह है कि हम मध्य की गणना कैसे करते हैं, यह देखते हुए कि हम जिस संख्या का परीक्षण कर रहे हैं, वह कई बार गिरफ्तारी में भी नहीं हो सकता है, क्योंकि अंत में, हम जिन संख्याओं का उपयोग कर रहे हैं वे केवल मनमानी संख्याएं हैं।
इसे समझाने के लिए हमें यह कल्पना करने की आवश्यकता है कि हमारा कार्यक्रम एक ऐसे चरण में है जहां निम्न और उच्च लगभग एक-दूसरे से टकराने वाले हैं। यदि हम अपेक्षा से कम संख्याएँ गिनते हैं, तो हम निम्न =मध्य + 1 सेट करेंगे, यह संभावित रूप से हमारे मध्य को 1 से बढ़ा देता है। और हमारे मध्य को 1 से बढ़ाकर, हम सुनिश्चित कर सकते हैं कि संख्याएँ गिरफ्तारी में शामिल हैं।
आउटपुट
कंसोल में आउटपुट होगा -
11