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

ภาพรวมปัญหา

ให้รายการตัวเลขและขนาดหน้าต่าง k เราต้องหาค่ามัธยฐาน (median) ของแต่ละหน้าต่างที่เลื่อนไปทีละหนึ่งตำแหน่งจากซ้ายไปขวา

ตัวอย่าง

อาเรย์: [1, 3, -1, -3, 5, 3, 6, 8], k = 3

ผลลัพธ์: [1, -1, -1, 3, 5, 6]

วิธีแก้ปัญหา

ใช้ Multiset (BST แบบสมดุล) เพื่อจัดเก็บองค์ประกอบในหน้าต่างปัจจุบัน เนื่องจาก Multiset จัดเก็บข้อมูลเรียงลำดับอัตโนมัติ จึงสามารถหาค่ามัธยฐานได้ในเวลา O(log k)

ขั้นตอนหลัก

1. สร้าง Multiset arr เพื่อเก็บค่าในหน้าต่าง
2. ฟังก์ชัน insert(x): เพิ่ม x เข้า arr
3. ฟังก์ชัน delete_(x): ลบ x ออกจาก arr (ถ้ามีอยู่)
4. ฟังก์ชัน getMedian():
   • ให้ n = arr.size()
   • หาตำแหน่งกลาง: a = *next(arr.begin(), n/2 - 1), b = *next(arr.begin(), n/2)
   • ถ้า n เป็นคี่ → คืนค่า b
   • ถ้า n เป็นคู่ → คืนค่า (a + b) * 0.5
5. เติมองค์ประกอบ k ตัวแรกเข้า arr
6. เลื่อนหน้าต่าง: ลบองค์ประกอบเก่าออก เพิ่มองค์ประกอบใหม่เข้า แล้วบันทึกค่ามัธยฐาน

โค้ด C++

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<double> 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 (n & 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;
    }
};

int main() {
    Solution ob;
    vector<int> v = {1, 3, -1, -3, 5, 3, 6, 8};
    print_vector(ob.medianSlidingWindow(v, 3));
}

การวิเคราะห์ความซับซ้อน

• เวลา: O(n log k) — แต่ละการแทรก/ลบ/หามัธยฐาน ใช้ O(log k)
• พื้นที่: O(k) — เก็บองค์ประกอบในหน้าต่าง

การทดสอบ

Input: {1,3,-1,-3,5,3,6,8}, k=3
Output: [1, -1, -1, 3, 5, 6]