最大化C ++中数组的中位数
问题陈述
给定一个由N个元素组成的数组arr[]和一个整数K，其中K<N。任务是将K个整数元素插入同一数组，以使结果数组的中位数最大化
如果输入数组为{1、3、2、5}且k=3，则-
排序后的数组变为{1,2,3,5}
插入3个大于5的元素。此操作数组变为{1、2、3、5、6、6、6}之后
新数组的中位数为5
算法
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
示例
#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;
}输出结果
当您编译并执行上述程序时。它生成以下输出-
Max median = 5
热门推荐
10 八一幼儿祝福语大全简短
11 公司乔迁食堂祝福语简短
12 婚礼结束聚餐祝福语简短
13 儿媳买车妈妈祝福语简短
14 毕业送礼老师祝福语简短
15 同事辞职正常祝福语简短
16 恭贺新婚文案祝福语简短
17 金店立秋祝福语简短英文
18 婆婆高寿祝福语大全简短