数据结构
网络
关系型数据库管理系统 (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 次浏览
广告