Trong bài toán này, chúng tôi đưa ra các truy vấn Q. Đây là ba loại, chúng -
-
Truy vấn 1:Thêm số N vào danh sách.
-
Truy vấn 2:Xóa số N khỏi danh sách.
-
Truy vấn 3:Trả về sự khác biệt của phần tử tối thiểu và tối đa của danh sách.
Nhiệm vụ của chúng tôi là tạo một chương trình để giải quyết các truy vấn để thêm, bớt và trả về sự khác biệt của giá trị tối đa và tối thiểu trong C ++.
Mô tả vấn đề
Chúng tôi sẽ nhận được Q số lượng truy vấn mà chúng tôi sẽ thực hiện trong danh sách. Có 3 loại truy vấn để thêm, bớt và tìm sự khác biệt của phần tử tối đa và tối thiểu của danh sách. Sử dụng mà trước tiên, chúng tôi sẽ xây dựng danh sách các phần tử và sau đó tìm giá trị Truy vấn 3 về sự khác biệt giữa các phần tử tối đa và tối thiểu của danh sách.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào :Q =6
Truy vấn (1, 4)
Truy vấn (1, 9)
Truy vấn (1, 6)
Truy vấn (2, 4)
Truy vấn (1, 3)
Truy vấn (3)
Đầu ra :6
Giải thích
Cuối cùng, danh sách sẽ là {9, 6, 3}.
Tối đa -> 9
Tối thiểu -> 3
Sự khác biệt -> 6
Phương pháp tiếp cận giải pháp
Một cách tiếp cận đơn giản để giải quyết vấn đề là sử dụng cách giải trực tiếp từng truy vấn. Bằng cách làm theo các bước sau−
-
Khởi tạo một mảng.
-
Đối với loại truy vấn 1, hãy thêm một phần tử vào mảng
-
Đối với loại truy vấn 2, hãy xóa một phần tử khỏi mảng
-
Đối với loại truy vấn 3, hãy tìm sự khác biệt giữa tối đa và tối thiểu và trả về giá trị.
Ví dụ
#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]);
}
} Đầu ra
The difference between the maximum and minimum elements of the list is 6
Quá trình tìm kiếm có thể hiệu quả hơn nếu chúng ta sử dụng các cấu trúc dữ liệu khác sau đó là một mảng đơn giản. Ở đây, nếu chúng ta sử dụng cây tìm kiếm nhị phân tự cân bằng thay vì mảng. Phần tử max sẽ ở cuối (được truy cập bằng phương thức rbegin ()). Và phần tử min sẽ ở đầu (được truy cập bằng phương thức begin ()).
Việc triển khai cây tìm kiếm nhị phân tự cân bằng trong C ++ được thực hiện bằng cách sử dụng tập hợp.
Ví dụ
#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]);
}
} Đầu ra
The difference between the maximum and minimum elements of the list is 6