数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学使用C++使中位数等于x的最小元素个数。
问题陈述
给定一个大小为n的数组“arr”和元素x，任务是找到要添加到数组中的最小元素数量，以使中位数等于x。
长度为n的数组中的中位数是在我们将元素按非递减顺序排序后占据(n-1)/2位置的元素。例如，在下面的数组中，中位数是20：
arr1[] = {10, 20, 30, 40}
如果arr[] = {1, 2, 3}且x = 4，则我们必须在数组中添加4个数字，即{4, 5, 5, 5}，以使中位数等于4。
算法
该算法非常简单。我们必须向数组中添加一个数字x，直到数组的中位数等于x。
示例
#include <iostream>
#include <algorithm>
using namespace std;
int minNumbersToBeAdded(int *arr, int n, int x){
sort(arr, arr + n);
int cnt = 0;
while (arr[(n - 1)/2] != x) {
arr[n] = x;
++n;
sort(arr, arr + n);
++cnt;
}
return cnt;
}
int main(){
int arr[20] = {1, 2, 3};
int x = 4;
int n = 3;
cout << "Minimum numbers to be added = " << minNumbersToBeAdded(arr, n, x) << endl;
return 0;
}输出
编译并执行上述程序时，它会生成以下输出：
Minimum numbers to be added = 4
更新于：2019年10月31日
浏览量：181
广告