जावास्क्रिप्ट में प्रत्येक विंडो के लिए माध्यिका ढूँढना

औसत

गणित में माध्यिका, माध्यिका एक क्रमबद्ध (क्रमबद्ध) पूर्णांक सूची में मध्य मान है।

यदि सूची का आकार सम है, और कोई मध्य मान नहीं है। माध्यिका दो मध्य मानों का माध्य (औसत) है।

समस्या

हमें एक जावास्क्रिप्ट फ़ंक्शन लिखने की आवश्यकता है जो पहले तर्क के रूप में इंटीजर, एआर की एक सरणी लेता है और दूसरे तर्क के रूप में एक संख्या संख्या (संख्या <=सरणी गिरफ्तारी की लंबाई) लेता है।

अब सरणी में आकार संख्या की प्रत्येक विंडो के लिए, हमारे फ़ंक्शन को माध्यिका की गणना करनी चाहिए और उस माध्य मान को एक नए सरणी में धकेलना चाहिए और अंत में पुनरावृत्ति के अंत में उस माध्यिका सरणी को वापस करना चाहिए।

उदाहरण के लिए, यदि फ़ंक्शन का इनपुट है -

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];

आउटपुट स्पष्टीकरण:

उदाहरण

इसके लिए कोड होगा -

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 ]