Tuyên bố vấn đề
Cho một mảng arr [] gồm N phần tử và một số nguyên K trong đó K
Nếu mảng đầu vào là {1, 3, 2, 5} và k =3 thì−
Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau−
Thuật toán
1. In order to maximize the median of the resultant array, all the elements that need to be inserted must be greater than the maximum element from the array
2. Sort the array and the median of the array will be arr[size / 2] if the size is odd else (arr[(size / 2) – 1] + arr[size / 2]) / 2
Ví dụ
#include <bits/stdc++.h>
using namespace std;
double getMaxMedian(int *arr, int n, int k){
int newSize = n + k;
double median;
sort(arr, arr + n);
if (newSize % 2 == 0) {
median = (arr[(newSize / 2) - 1] + arr[newSize / 2]) / 2;
return median;
}
median = arr[newSize / 2];
return median;
}
int main(){
int arr[] = {1, 3, 2, 5};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;
cout << "Max median = " << getMaxMedian(arr, n, k) << endl;
return 0;
}
Đầu ra
Max median = 5