Trung vị cửa sổ trượt trong C++

Cho một danh sách các số và kích thước cửa sổ k, bài toán yêu cầu tìm danh sách các trung vị khi cửa sổ trượt từ trái sang phải qua mảng.

Ví dụ minh họa

Với mảng [1, 3, -1, -3, 5, 3, 6, 8] và k = 3, các cửa sổ và trung vị tương ứng:

Kết quả: [1, -1, -1, 3, 5, 6]

Thuật toán

Sử dụng multiset (cây cân bằng) để duy trì các phần tử trong cửa sổ theo thứ tự đã sắp xếp, cho phép chèn, xóa và truy cập phần tử giữa trong O(log k).

• Khởi tạo multiset arr rỗng.
• Chèn k phần tử đầu tiên vào arr.
• Với mỗi bước trượt:
  • Tính trung vị từ arr.
  • Xóa phần tử cũ nhất (bên trái cửa sổ).
  • Chèn phần tử mới (bên phải cửa sổ).
• Cuối cùng thêm trung vị của cửa sổ cuối.

Tính trung vị từ multiset

• Nếu số phần tử lẻ: lấy phần tử ở vị trí n/2 (0-indexed).
• Nếu chẵn: lấy trung bình của hai phần tử ở vị trí n/2 - 1 và n/2.

Cài đặt 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));
    return 0;
}

Độ phức tạp

• Thời gian: O(n log k) — mỗi lần chèn/xóa/truy cập trung vị tốn O(log k), lặp n lần.
• Không gian: O(k) — lưu trữ tối đa k phần tử trong multiset.

Input / Output

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