数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究使用 C++ 统计中位数也在子集中出现的子集数量
给定一个包含正数的数组 arr[]。目标是找到 arr[] 元素的子集，使得子集的值的中位数也存在于该集合中。
例如
输入
arr[] = { 1,2,3 }输出
Count of number of subsets whose median is also present in the same subset are: 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 }输出
Count of number of subsets whose median is also present in the same subset are: 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) * check(n − r) 和 temp_2=check(n) / temp。返回计算出的值 tem_2。
函数 power(int n, int r) 获取 n 和 r 并返回 nr 的值。
如果 r 为 0，则答案将为 1，因此返回 1。
取 total = power(n, r / 2)。( nr/2)
使用 total2 % mod 更新 total。其中 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 = (count + com(temp_3 + temp_2, temp_3)) % mod。
在 while 循环结束时，我们将拥有 count。
返回 count 作为结果。
示例
#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<<"Count of number of subsets whose median is also present in the same subset are: "<<median_subset(arr, size);
return 0;
}输出
如果我们运行以上代码，它将生成以下输出 -
Count of number of subsets whose median is also present in the same subset are: 9
171 次查看
