সমস্যা
ধরুন, আমাদের কাছে সংখ্যার বিন্যাসের একটি সাজানো বিন্যাস রয়েছে (ক্রমবর্ধমান ক্রম অনুসারে সাজানো) -
const arr = [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15] ];
আমাদের একটি জাভাস্ক্রিপ্ট ফাংশন লিখতে হবে যা প্রথম আর্গুমেন্টের মতো একটি অ্যারে এবং দ্বিতীয় আর্গুমেন্ট হিসাবে একটি একক পূর্ণসংখ্যা, 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
যদি লক্ষ্যটি সূচকের মাঝামাঝি সংখ্যার চেয়ে বেশি হয়, তাহলে আমরা ডান অংশটি অনুসন্ধান করি, যদি এটি ছোট হয় তবে আমরা বাম দিকে অনুসন্ধান করি।
যাইহোক, এই 2d arr সাজানো অ্যারেতে, এরকম একটি মধ্য সূচক খুঁজে পাওয়া অসম্ভব। এখানে অন্তর্দৃষ্টি হল আমাদের k এর বিরুদ্ধে পরীক্ষা করার জন্য সংখ্যার একটি পরিসীমা ব্যবহার করা। আমরা জানি প্রথম সংখ্যাটি সবচেয়ে ছোট এবং শেষ সংখ্যাটি সবচেয়ে বড়, এর মানে আমাদের লক্ষ্য সংখ্যাটি এর মধ্যে কিছু হতে হবে। আমরা এই দুটি সংখ্যাকে আমাদের নিম্ন এবং উচ্চ হিসাবে ব্যবহার করতে পারি, এবং আমাদের মধ্যকে মাঝখানের সংখ্যা হিসাবে সেট করতে পারি, এবং arr-এ কতগুলি সংখ্যা সেই সংখ্যার চেয়ে ছোট তা পরীক্ষা করে দেখতে পারি এবং সেই অনুযায়ী নিম্ন এবং উচ্চ সমন্বয় করতে পারি।
যখন আমরা ঠিক k সংখ্যা পাই, আমরা জানি আমরা আমাদের উত্তর খুঁজে পেয়েছি। এখানে অত্যন্ত জটিল অংশটি হল যে আমরা কীভাবে মাঝামাঝি গণনা করি তা দেখে, অনেকবার আমরা যে সংখ্যার বিপরীতে পরীক্ষা করছি তা অ্যারেতেও নাও হতে পারে, কারণ শেষ পর্যন্ত, আমরা যে সংখ্যাগুলি ব্যবহার করছি তা কেবলমাত্র নির্বিচারে সংখ্যা৷
এটি ব্যাখ্যা করার জন্য আমাদের কল্পনা করতে হবে যে আমাদের প্রোগ্রামটি এমন একটি পর্যায়ে যেখানে নিম্ন এবং উচ্চ প্রায় একে অপরকে আঘাত করতে চলেছে। যদি আমরা প্রত্যাশিত সংখ্যার চেয়ে কম সংখ্যা গণনা করি, তাহলে আমরা low=mid+1 সেট করব, এটি সম্ভাব্যভাবে আমাদের মধ্যকে 1 দ্বারা বৃদ্ধি করে। এবং আমাদের মধ্য 1কে 1 দ্বারা বৃদ্ধি করে, আমরা নিশ্চিত করতে পারি যে সংখ্যাগুলি অ্যাআর-এ অন্তর্ভুক্ত করা হয়েছে।
আউটপুট
কনসোলে আউটপুট হবে −
11
