資料結構
網路
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 瀏覽量
廣告