แบบสอบถามเพื่อเพิ่ม ลบ และส่งคืนส่วนต่างของค่าสูงสุดและต่ำสุดใน C++

ในปัญหานี้ เราได้รับคำถาม Q เหล่านี้มีสามประเภท ได้แก่ −

• คำถามที่ 1:เพิ่มหมายเลข N ในรายการ

• แบบสอบถาม 2:ลบหมายเลข N ออกจากรายการ

• แบบสอบถาม 3:ส่งคืนค่าส่วนต่างขององค์ประกอบต่ำสุดและสูงสุดของรายการ

งานของเราคือการสร้างโปรแกรมเพื่อแก้ปัญหาการสืบค้นเพื่อเพิ่ม ลบ และส่งคืนส่วนต่างของค่าสูงสุดและต่ำสุดใน C++

คำอธิบายปัญหา

เราจะได้รับคำถามจำนวน Q ที่เราจะดำเนินการในรายการ คิวรีมี 3 ประเภทที่จะเพิ่ม ลบ และค้นหาความแตกต่างขององค์ประกอบสูงสุดและต่ำสุดของรายการ โดยเราจะสร้างรายการองค์ประกอบก่อน จากนั้นจึงค้นหาค่า Query 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()) และองค์ประกอบขั้นต่ำจะอยู่ที่จุดเริ่มต้น (เข้าถึงได้โดยใช้วิธี start())

การนำแผนผังการค้นหาไบนารีที่ปรับสมดุลในตัวเองมาใช้ใน C++ ทำได้โดยใช้ชุด

ตัวอย่าง

#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