ค่ามัธยฐานของหน้าต่างบานเลื่อนใน C ++

สมมติว่าเรามีรายการตัวเลข และเรามีหน้าต่างขนาด k หนึ่งหน้าต่าง เราต้องหารายการค่ามัธยฐานโดยใช้ลักษณะหน้าต่างบานเลื่อน ดังนั้นหากการกระจายเป็นเหมือนด้านล่าง −

ที่นี่เราได้พิจารณา k เป็น 3 และผลลัพธ์จะเป็น [1,-1,-1,3,5,6]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดหนึ่งชุด arr
• กำหนดฟังก์ชัน insert() ซึ่งจะใช้ x
• แทรก x ลงใน arr
• กำหนดฟังก์ชัน delete_() ซึ่งจะใช้ x
• ลบ x ออกจาก arr หากมีอยู่
• กำหนดฟังก์ชัน getMedian()
• n :=ขนาดของ arr
• a :=ข้ามไปที่ n/2 – 1 ก้าวไปข้างหน้าขององค์ประกอบแรกของ arr และรับค่า
• b :=ข้ามไปที่ n/2 ก้าวไปข้างหน้าขององค์ประกอบแรกของ arr และรับค่า
• ถ้าขนาดของ arr แล้ว −
  • คืน b
• ผลตอบแทน (a + b) * 0.5
• จากวิธีหลักให้ทำดังนี้
• กำหนดอาร์เรย์และ
• ล้างอาร์เรย์ arr
• สำหรับการเริ่มต้น i :=0 เมื่อฉัน
• เรียกฟังก์ชัน insert(nums[i])

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
public:
   multiset <double> arr;
   void insert(double x){
      arr.insert(x);
   }
   void delete_(double x){
      arr.erase(arr.find(x));
   }
   double getMedian(){
      int n = arr.size();
      double a = *next(arr.begin(), n / 2 - 1);
      double b = *next(arr.begin(), n / 2);
      if(arr.size() & 1)return b;
      return (a + b) * 0.5;
   }
   vector<double> medianSlidingWindow(vector<int>& nums, int k) {
      vector <double> ans;
      arr.clear();
      for(int i = 0; i < k; i++){
         insert(nums[i]);
      }
      for(int i = k, j = 0; i < nums.size(); i++, j++){
         ans.push_back(getMedian());
         delete_(nums[j]);
         insert(nums[i]);
      }
      ans.push_back(getMedian());
      return ans;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,3,-1,-3,5,3,6,8};
   print_vector(ob.medianSlidingWindow(v, 3));
}

อินพุต

{1,3,-1,-3,5,3,6,8}

ผลลัพธ์

[1, -1, -1, 3, 5, 6, ]