数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会科学
时尚研究
法律研究在 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
更新日期： 2019 年 12 月 24 日
194 次浏览
广告