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