माध्यिका
गणित में, माध्यिका एक क्रमबद्ध (सॉर्टेड) पूर्णांक सूची में मध्य मान होता है।
यदि सूची का आकार सम है, और कोई मध्य मान नहीं है। माध्यिका दो मध्य मानों का औसत (माध्य) होता है।
समस्या
हमें एक JavaScript फ़ंक्शन लिखना है जो पहली आर्ग्युमेंट के रूप में पूर्णांकों की एक सरणी arr और दूसरी आर्ग्युमेंट के रूप में संख्या num (num <= arr.length) लेता है।
अब सरणी arr में आकार 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 ]
