使用C ++要使中位数等于x的最小元素数量。
问题陈述
给定大小为n且元素x的数组“arr”，任务是找到要添加到数组中的最小元素数，以使中位数等于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