使用C ++要使中位数等于x的最小元素数量。

  • Z时代
  • 2024-01-10
  • 分类：综合

问题陈述

给定大小为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

以上是 使用C ++要使中位数等于x的最小元素数量。 的全部内容， 来源链接： utcz.com/z/351485.html

回到顶部