计算中位数也出现在C ++中同一子集中的子集数量

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

给定一个包含正数的数组arr []。目的是找到arr []元素的子集，以使子集的值的中值也出现在该集合中。

例如

输入值

arr[] = { 1,2,3 }
输出结果
中位数也出现在同一子集中的子集数量计数为： 4

说明

The sets with their medians in that same set are:
[ 1 ], median is 1
[ 2 ], median is 2
[ 3 ], median is 3
[ 1,2,3 ], median is 2

输入值

arr[] = { 4,6,5 }
输出结果
中位数也出现在同一子集中的子集数量计数为： 4

说明

The sets with their medians in that same set are:
[ 4 ], [ 6 ], [ 5 ], [ 4,6,5 ],

以下程序中使用的方法如下-

在这种方法中，我们将检查偶数和奇数大小的元素。然后，我们可以基于以下事实找到中位数：对于奇数个项目，中位数与中间元素存在于同一集合中。因此我们将2n-1加到计数中。对于偶数长度的子集，我们将检查是否存在两个相同的元素，因此请计算具有两个中间元素的偶数长度的子集。

  • 取正数的数组arr []。

  • 功能 median_subset(arr, size) 取arr并返回中位数也出现在同一子集中的子集数的计数。

  • 功能 check(int temp) 接受一个整数并使用从i = 2到i <= temp的for循环返回该数字的阶乘。

  • 计算count = count * i，并在循环结束时将其作为阶乘返回。

  • 功能 com(int n, int r)取n和r并返回组合nCr的值。在此内取temp =check(r) *检查(n-r)和temp_2 =check(n)/温度 返回tem_2作为计算值。

  • 功能 power(int n, int r) 取n和r并返回nr的值。

  • 如果r为0，则答案为1，因此返回1。

  • 取总=功率（n，r / 2）。（nr / 2）

  • 总计更新2％mod。其中mod = 1000000007。

  • 如果r是偶数，则将temp返回为（total * n）％mod，否则返回total。

  • 内部功能 median_subset()，将count作为count = power（2，size − 1），它是奇数长度子集的数量。

  • 使用sort（arr，arr + size）对数组arr []进行排序。

  • 使用while循环，我们将检查最左边中间元素的每个元素，直到它们相等为止。

  • 将temp_2 = size − 1 − temp作为最严格的中间元素右侧的元素数。

  • 将temp_3 = i作为最左边中间元素左侧的元素数量。

  • 添加选定的偶数长度子集以计算为count =（count + com（temp_3 + temp_2，temp_3））％mod。

  • 在while循环结束时，我们将进行计数。

  • 返回计数作为结果。

示例

#include <algorithm>
#include <iostream>
using namespace std;
#define mod 1000000007;
int check(int temp){
   int count = 1;
   for (int i = 2; i <= temp; i++){
      count = count * i;
   }
   return count;
}
int com(int n, int r){
   int temp = check(r) * check(n − r);
   int temp_2 = check(n) / temp;
   return temp_2;
}
int power(int n, int r){
   if (r == 0){
      return 1;
   }
   int total = power(n, r / 2);
   total = (total * total) % mod;
   if (r % 2){
      int temp = (total * n) % mod;
      return temp;
   } else {
      return total;
   }
}
int median_subset(int* arr, int size){
   int count = power(2, size − 1);
   sort(arr, arr + size);
   for (int i = 0; i < size; ++i){
      int temp = i + 1;
      while (temp < size && arr[temp] == arr[i]){
         int temp_2 = size − 1 − temp;
         int temp_3 = i;
         count = (count + com(temp_3 + temp_2, temp_3)) % mod;
         temp++;
      }
   }
   return count;
}
int main(){
   int arr[] = { 4, 5, 4, 6 };
   int size = sizeof(arr) / sizeof(arr[0]);
   cout<<"中位数也出现在同一子集中的子集数量计数为： "<<median_subset(arr, size);
   return 0;
}
输出结果

如果我们运行上面的代码，它将生成以下输出-

中位数也出现在同一子集中的子集数量计数为： 9

以上是 计算中位数也出现在C ++中同一子集中的子集数量 的全部内容， 来源链接： utcz.com/z/326298.html

回到顶部