資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學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
for i := 0 to nums.length -1:
建立名為que_max的優先佇列
建立名為que_min的另一個優先佇列
for j := i to nums.length -1:
將nums[j]插入que_max
while que_max.size() >= 2:
將que_max的頂部元素插入que_min
從que_max刪除頂部元素
while (que_min.size() != 0 and que_max.top() > que_min.top()):
a := que_max.top(), 從que_max刪除頂部元素
b := que_min.top(), 從que_min刪除頂部元素
將b插入que_max
將a插入que_min
if i mod 2 == j mod 2:
ret := ret + que_max.top()
return 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
更新於：2020-12-25
214 次瀏覽
廣告