程序查找C ++中所有奇数长度子列表的中位数之和
假设我们有一个称为nums的数字列表，我们必须找到给定列表的每个奇长子列表的中位数之和。
因此，如果输入像nums = [2，4，6，3]，那么输出将是23，因为奇数子列表是-[2]，[4]，[6]，[3]， [2，4，6]，[4，6，3]，因此中位数的总和为2 + 4 + 6 + 3 + 4 + 4 = 23
为了解决这个问题，我们将遵循以下步骤-
ret：= 0
对于初始化i：= 0，当i <nums大小时，更新（将i增加1），执行-
将nums [j]插入que_max
而que_max的大小> = 2，则执行-
while（que_min的大小不为0且que_max的顶部元素> que_min的顶部元素），执行-
如果i mod 2与j mod 2相同，则-
将que_max的顶部元素插入que_min
从que_max中删除top元素
a：= que_max的顶部元素，从que_max中删除顶部元素
b：= que_min的顶部元素，从que_min中删除顶部元素
将b插入que_max
插入que_min
ret：= ret + que_max的顶部元素
定义优先级队列que_max
定义另一个名为que_min的优先级队列
对于初始化j：= i，当j <nums的大小时，更新（j增加1），-
返回ret
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h>using namespace std;
int solve(vector<int>& nums) {
int ret = 0;
for (int i = 0; i < nums.size(); i++) {
priority_queue<int> que_max;
priority_queue<int, vector<int>, greater<int>> que_min;
for (int j = i; j < nums.size(); j++) {
que_max.push(nums[j]);
while (que_max.size() - que_min.size() >= 2) {
que_min.push(que_max.top());
que_max.pop();
}
while (que_min.size() && que_max.top() > que_min.top()) {
int a = que_max.top();
que_max.pop();
int b = que_min.top();
que_min.pop();
que_max.push(b);
que_min.push(a);
}
if (i % 2 == j % 2) {
ret += que_max.top();
}
}
}
return ret;
}
int main(){
vector<int> v = {2, 4, 6, 3};
cout << solve(v);
}
输入值
{2, 4, 6, 3}输出结果23
以上是 程序查找C ++中所有奇数长度子列表的中位数之和 的全部内容， 来源链接： utcz.com/z/361967.html
