数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会研究
时尚研究
法律研究在 C++ 中向同一数组添加 K 个元素后最大化给定数组的中值
问题陈述
给定一个 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
201 浏览量
广告