資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++中新增、刪除和返回最大值與最小值之差的查詢
在這個問題中，我們給定Q個查詢。它們有三種類型：
查詢1：將數字N新增到列表中。
查詢2：從列表中刪除數字N。
查詢3：返回列表中最小元素和最大元素的差。
我們的任務是建立一個程式來解決在C++中新增、刪除和返回最大值與最小值之差的查詢。
問題描述
我們將得到Q個查詢，這些查詢將對列表執行操作。有3種類型的查詢：新增、刪除以及查詢列表中最大元素和最小元素的差值。我們將首先使用這些查詢構建元素列表，然後找到列表中最大元素和最小元素之差（查詢3的值）。
讓我們舉個例子來理解這個問題：
輸入：Q = 6
查詢 (1, 4)
查詢 (1, 9)
查詢 (1, 6)
查詢 (2, 4)
查詢 (1, 3)
查詢 (3)
輸出: 6
解釋
最後，列表將是 {9, 6, 3}。
最大值 -> 9
最小值 -> 3
差值 -> 6
解決方案方法
解決這個問題的一個簡單方法是直接解決每個查詢。透過以下步驟：
初始化一個數組。
對於查詢型別1，將元素新增到陣列中。
對於查詢型別2，從陣列中刪除元素。
對於查詢型別3，找到最大值和最小值之間的差值，並返回該值。
示例
#include <iostream>
using namespace std;
void solveQuerry(int type, int item){
int list[100];
static int index = 0;
if(type == 1){
list[index] = item;
index++;
}
else if(type == 2){
for(int i = 0; i <= index; i++)
if(list[i] == item ){
list[i] = 0;
break;
}
}
else if(type == 3){
int max = -100, min = 100;
for(int i = 0; i< index; i++){
if(list[i] == 0)
i++;
if(list[i] > max)
max = list[i];
if(list[i] < min)
min = list[i];
}
cout<<"The difference between the maximum and minimum elements of the list is "<<(max - min);
}
}
int main() {
int Q = 6;
int query[Q][2] = {{1, 5}, {1, 9}, {1, 6}, {2, 4}, {1, 3}, {3, 0}};
for(int i = 0; i< Q; i++){
solveQuerry(query[i][0], query[i][1]);
}
}輸出
The difference between the maximum and minimum elements of the list is 6
如果我們使用比簡單陣列更有效的資料結構，搜尋過程可以更高效。在這裡，如果我們使用自平衡二叉搜尋樹而不是陣列，最大元素將位於末尾（使用rbegin()方法訪問）。最小元素將位於開頭（使用begin()方法訪問）。
C++中自平衡二叉搜尋樹的實現是使用集合（set）。
示例
#include <bits/stdc++.h>
using namespace std;
set<int> myList;
void solveQuerry(int type, int num){
if(type == 1){
myList.insert(num);
}
else if(type == 2){
myList.erase(num);
}
else if(type == 3){
int max = *(myList.rbegin());
int min = *(myList.begin());
cout<<"The difference between the maximum and minimum elements of the list is "<<(max - min);
}
}
int main() {
int Q = 6;
int query[Q][2] = {{1, 5}, {1, 9}, {1, 6}, {2, 4}, {1, 3}, {3, 0}};
for(int i = 0; i< Q; i++){
solveQuerry(query[i][0], query[i][1]);
}
}輸出
The difference between the maximum and minimum elements of the list is 6
更新於：2020年10月9日
105 次瀏覽
廣告