Giả sử chúng ta có một danh sách các số, và chúng ta có một kích thước cửa sổ là k, chúng ta phải tìm danh sách các phương tiện bằng cách sử dụng cửa sổ trượt. Vì vậy, nếu phân phối như dưới đây -
| Vị trí cửa sổ | Trung vị | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| 1 | 3 | - 1 | -3 | 5 | 3 | 6 | 8 | 1 | |
| 1 | 3 | - 1 | - 3 | 5 | 3 | 6 | 8 | - 1 | |
| 1 | 3 | - 1 | - 3 | 5 | 3 | 6 | 8 | - 1 | |
| 1 | 3 | -1 | - 3 | 5 | 3 | 6 | 8 | 3 | |
| 1 | 3 | -1 | -3 | 5 | 3 | 6 | 8 | 5 | |
| 1 | 3 | -1 | -3 | 5 | 3 | 6 | 8 | 6 | |
Ở đây chúng ta đã coi k là 3 và kết quả sẽ là [1, -1, -1,3,5,6]
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- Xác định một bộ arr
- Xác định một hàm insert (), điều này sẽ lấy x,
- chèn x vào arr
- Xác định một hàm delete_ (), điều này sẽ lấy x,
- xóa x khỏi arr, nếu điều này tồn tại
- Xác định một hàm getMedian ()
- n:=kích thước của arr
- a:=nhảy đến n / 2 - 1 bước về phía trước của phần tử đầu tiên của arr và nhận giá trị
- b:=nhảy tới n / 2 bước tiến của phần tử đầu tiên của arr và nhận giá trị
- nếu kích thước của arr, thì -
- trả lại b
- return (a + b) * 0,5
- Từ phương thức chính, hãy làm như sau
- Xác định ans mảng
- xóa arr mảng
- để khởi tạo i:=0, khi i
- gọi hàm chèn (nums [i])
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#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));
} Đầu vào
{1,3,-1,-3,5,3,6,8} Đầu ra
[1, -1, -1, 3, 5, 6, ]