資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++中雙調序列插入元素的查詢
在這個問題中，我們給定一個雙調序列和Q個查詢。每個查詢包含一個整數x。我們的任務是在每次查詢後列印插入整數後的雙調序列長度。最後列印雙調序列。
問題描述 − 在這裡，我們給定一個雙調序列。並且有Q個查詢，每個查詢包含一個要新增到序列中的整數。我們將從每個查詢中新增元素到序列中，然後返回雙調序列的長度。所有查詢完成後，我們將列印雙調序列。
雙調序列是一種特殊的序列型別，它先遞增到一個點（稱為雙調點），然後遞減。
示例 − 1, 5, 6, 8, 9, 7, 5, 2
讓我們來看一個例子來更好地理解這個問題：
輸入
bseq = {1, 4, 6, 5, 2, 1}
Q = 2
Query = {5, 6 }輸出
7 7
{1, 4, 5, 6, 5, 2, 1 }解釋
對於第一個查詢，要插入的值是5，它可以插入到序列的遞增部分，形成序列{1, 4, 5, 6, 5, 2, 1}，長度為7。
對於第一個查詢，要插入的值是6，因為6是最大值，所以不能插入。因此，6不會被插入。
最終序列{1, 4, 5, 6, 5, 2, 1}，長度為7。
為了解決這個問題，我們將不得不把雙調序列分成兩個集合，一個用於序列的遞增部分直到最大值。另一個用於序列的遞減部分。
現在，對於每個要插入的元素，可能有以下幾種情況：
情況1（如果元素大於最大值） − 將元素新增到遞增序列的末尾，並更新最大值。
情況2 − 如果元素小於最大值，則首先在遞增集合中檢查元素是否存在，如果不存在則插入。否則，在遞減集合中搜索並新增（如果可能）。
情況3（如果元素等於最大值或該值同時存在於遞增和遞減集合中） − 則不能新增該元素。
每次查詢操作後，我們將透過新增兩個集合的長度來找到雙調序列的集合，
length(bseq) = length(incSet) + length(decSet)
所有查詢完成後，透過列印incSet，然後列印decSet來列印雙調序列。
程式說明我們解決方案的工作原理：
示例
#include <bits/stdc++.h>
using namespace std;
void calcBitonicSeqLenth(int bSeq[], int n, int query[], int Q){
int maxVal = INT_MIN;
for (int i = 0; i < n; i++)
maxVal = max(maxVal, bSeq[i]);
set <int> incSet, decSet;
incSet.insert(bSeq[0]);
decSet.insert(bSeq[n - 1]);
for (int i = 1; i < n; i++)
if (bSeq[i] > bSeq[i - 1])
incSet.insert(bSeq[i]);
for (int i = n - 2; i >= 0; i--)
if (bSeq[i] > bSeq[i + 1])
decSet.insert(bSeq[i]);
decSet.erase(decSet.find(maxVal));
for (int i = 0; i < Q; i++) {
if (maxVal <= query[i]) {
maxVal = query[i];
incSet.insert(query[i]);
}
else {
if (incSet.find(query[i]) == incSet.end())
incSet.insert(query[i]);
else
decSet.insert(query[i]);
}
int length = incSet.size() + decSet.size();
cout<<"For query "<<(i+1)<<": The length of Bitonic Sequence is "<<length<<endl;
}
cout<<"The Bitonic Sequence at the end of all queries is : ";
set<int>::iterator it;
for (it = incSet.begin(); it != incSet.end(); it++)
cout<<(*it)<<" ";
set<int>::reverse_iterator revIt;
for (revIt = decSet.rbegin(); revIt != decSet.rend(); revIt++)
cout<<(*revIt)<<" ";
}
int main(){
int bSeq[] = { 1, 4, 6, 5, 2, 1 };
int n = sizeof(bSeq) / sizeof(bSeq[0]);
int Q = 2;
int query[] = { 6, 5 };
calcBitonicSeqLenth(bSeq, n, query, Q);
return 0;
}輸出
For query 1: The length of Bitonic Sequence is 6 For query 2: The length of Bitonic Sequence is 7 The Bitonic Sequence at the end of all queries is : 1 4 5 6 5 2 1
更新於：2020年9月9日
69 次瀏覽
廣告