Ở đây chúng ta sẽ xem cách lấy trung vị của hai mảng đã sắp xếp cùng kích thước. Chúng ta sẽ dùng C++ STL để lưu trữ các phần tử mảng. Sau khi có hai mảng, chúng ta sẽ gộp chúng thành một. Vì hai mảng cùng kích thước được gộp, mảng cuối sẽ luôn chứa số chẵn phần tử. Chúng ta cần lấy hai phần tử giữa, sau đó lấy trung bình của chúng cho trung vị.
Thuật toán
median(arr1, arr2)
Begin arr3 := array after merging arr1 and arr2 sort arr3 len := length of arr3 mid := len/2 median := (arr3[mid] + arr3[mid-1])/2 return median End
Ví dụ
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
float median(vector<int> arr1, vector<int> arr2) {
vector arr3(arr1.size() + arr2.size());
merge(arr1.begin(), arr1.end(), arr2.begin(), arr2.end(), arr3.begin());
sort(arr3.begin(), arr3.end());
int len = arr3.size();
int mid = len/2;
return float(arr3[mid] + arr3[mid-1])/2;
}
main() {
vector<int> arr1 = {1, 3, 4, 6, 7};
vector<int> arr2 = {4, 5, 7, 8, 9};
cout << "Median: " << median(arr1, arr2);
}Kết quả
Median: 5.5