समस्या
मान लीजिए, हमारे पास संख्याओं की सरणियों की एक क्रमबद्ध सरणी है (बढ़ते क्रम में क्रमबद्ध) जैसे -
const arr = [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15] ];
हमें एक JavaScript फ़ंक्शन लिखना है जो ऐसी एक सरणी को पहले आर्गुमेंट के रूप में और एक पूर्णांक num को दूसरे आर्गुमेंट के रूप में लेता है।
हमारा फ़ंक्शन सरणी arr में मौजूद numवें सबसे छोटे तत्व को वापस करने वाला है।
उदाहरण के लिए, यदि फ़ंक्शन का इनपुट है -
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
यदि लक्ष्य इंडेक्स mid पर संख्या से बड़ा है, तो हम दाएं भाग को खोजते हैं, यदि यह छोटा है, तो हम बाएं को खोजते हैं।
हालांकि, इस 2D क्रमबद्ध सरणी में, ऐसा mid इंडेक्स ढूंढना असंभव है। यहां अंतर्ज्ञान संख्याओं की एक श्रृंखला का उपयोग करके हमारे k के खिलाफ परीक्षण करना है। हम जानते हैं कि पहली संख्या सबसे छोटी है और अंतिम संख्या सबसे बड़ी है, इसका मतलब है कि हमारी लक्ष्य संख्या बीच में कुछ होनी चाहिए। हम उन दो संख्याओं को अपने low और high के रूप में उपयोग कर सकते हैं, और अपने mid को बीच की संख्या पर सेट कर सकते हैं, और जांच सकते हैं कि सरणी में कितनी संख्याएं उस संख्या से छोटी हैं और तदनुसार low और high को समायोजित कर सकते हैं।
जब हमें ठीक k संख्याएं मिलती हैं, तो हम जानते हैं कि हमें अपना उत्तर मिल गया है। यहां बेहद मुश्किल हिस्सा यह है कि सिर्फ यह देखकर कि हम mid की गणना कैसे करते हैं, कई बार हम जिस संख्या के खिलाफ परीक्षण कर रहे हैं वह सरणी में भी नहीं हो सकती है, क्योंकि अंत में, हम जिन संख्याओं का उपयोग कर रहे हैं वे सिर्फ मनमानी संख्याएं हैं।
इसे समझाने के लिए हमें कल्पना करने की जरूरत है कि हमारा प्रोग्राम एक ऐसे चरण में है जहां low और high लगभग एक-दूसरे को छूने वाले हैं। यदि हमने अपेक्षा से कम संख्याएं गिनीं, तो हम low=mid+1 सेट करेंगे, यह संभावित रूप से हमारे mid को सिर्फ 1 से बढ़ाता है। और 1 से 1 करके अपने mid को बढ़ाकर, हम यह सुनिश्चित कर सकते हैं कि संख्याएं सरणी में शामिल हैं।
आउटपुट
कंसोल में आउटपुट होगा -
11
