Tối đa hóa trung vị của mảng đã cho sau khi thêm K phần tử vào cùng một mảng trong C ++

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ì -

• Mảng đã sắp xếp trở thành {1, 2, 3, 5}
• Chèn 3 phần tử lớn hơn 5. Sau khi mảng hoạt động này trở thành {1, 2, 3, 5, 6, 6, 6}
• Giá trị trung bình của mảng mới là 5

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

Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra đầu ra sau:

Max median = 5