মিডিয়ান
গণিতে মিডিয়ান হলো একটি সোর্টেড ইন্টিজার লিস্টের মাঝপথের মান। যদি লিস্টের আকার জোড় হয় (মাঝপথের মান নেই), তবে মিডিয়ান হবে দুটি মাঝপথের মানের গড় (মিন) মান।
সমস্যা
আমাদের একটি জাভাস্ক্রিপ্ট ফাংশন লিখতে হবে যা একটি ইন্টিজার অ্যারে arr প্রথম আর্গুমেন্ট ও একটি সংখ্যা num (num <= arr.length) دومা আর্গুমেন্ট হিসেবে নেবে।
অ্যারেতে আকার num এর প্রতিটি উইন্ডোর জন্য মিডিয়ান গণনা করে একটি নতুন অ্যারেতে পুশ করবে এবং শেষে সেটি রিটার্ন করবে।
উদাহরণ:
const arr = [5, 3, 7, 5, 3, 1, 8, 9, 2, 4, 6, 8]; const num = 3;
আউটপুট হবে:
const output = [5, 5, 5, 3, 3, 8, 8, 4, 4, 6];
আউটপুট ব্যাখ্যা:
| শুরু ইন্ডেক্স | কারেন্ট উইন্ডো | সোর্টেড উইন্ডো | মিডিয়ান |
|---|---|---|---|
| 0 | [5, 3, 7] | [3, 5, 7] | 5 |
| 1 | [3, 7, 5] | [3, 5, 7] | 5 |
| 2 | [7, 5, 3] | [3, 5, 7] | 5 |
| 3 | [5, 3, 1] | [1, 3, 5] | 3 |
| 4 | [3, 1, 8] | [1, 3, 8] | 3 |
| 5 | [1, 8, 9] | [1, 8, 9] | 8 |
| 6 | [8, 9, 2] | [2, 8, 9] | 8 |
| 7 | [9, 2, 4] | [2, 4, 9] | 4 |
| 8 | [2, 4, 6] | [2, 4, 6] | 4 |
| 9 | [4, 6, 8] | [4, 6, 8] | 6 |
উদাহরণ
কোডটি নিচের মতো (বাইনারি সার্চ দিয়ে স্লাইডিং উইন্ডো মেইনটেইন):
const arr = [5, 3, 7, 5, 3, 1, 8, 9, 2, 4, 6, 8]; const num = 3; const binarySearch = (arr, target, l, r) => { while (l < r) { const mid = Math.floor((l + r) / 2); if (arr[mid] < target) l = mid + 1; else if (arr[mid] > target) r = mid; else return mid; }; if (l === r) return arr[l] >= target ? l : l + 1; } const medianSlidingWindow = (arr = [], num = 1) => { let l = 0, r = num - 1, res = []; const window = arr.slice(l, num); window.sort((a, b) => a - b); while (r < arr.length) { const median = num % 2 === 0 ? (window[Math.floor(num / 2) - 1] + window[Math.floor(num / 2)]) / 2 : window[Math.floor(num / 2)]; res.push(median); let char = arr[l++]; let index = binarySearch(window, char, 0, window.length - 1); window.splice(index, 1); char = arr[++r]; index = binarySearch(window, char, 0, window.length - 1); window.splice(index, 0, char); } return res; }; console.log(medianSlidingWindow(arr, num)); কোড ব্যাখ্যা:
স্লাইডিং উইন্ডো হাতে বাইনারি সার্চ দিয়ে সঠিক পজিশনে এলিমেন্ট ইনসার্ট ও রিমুভ করে সর্টেড অর্ডার মেইনটেইন করা হয়েছে।
আউটপুট
কনসোলে আউটপুট:
[5, 5, 5, 3, 3, 8, 8, 4, 4, 6 ]
