Computer >> Máy Tính >  >> Lập trình >> C ++

Truy vấn phạm vi tối thiểu trong mảng trong C ++

Cho một mảng Arr [] chứa N phần tử. Mục tiêu là tìm giá trị nhỏ nhất và lớn nhất từ ​​các chỉ mục của truy vấn.

Theo truy vấn, chúng tôi được cung cấp chỉ mục bắt đầu và chỉ mục kết thúc.

Ví dụ

Trong - Arr [] ={1, 2, 3, 4, 5} QStart =1 QEnd =4

Hết -

Giá trị tối thiểu:2

Giá trị tối đa:5

Giải thích −Trong các truy vấn trên, chỉ mục bắt đầu là 1 và chỉ mục kết thúc là 4. Giữa hai chỉ mục này, giá trị nhỏ nhất trong Arr là 2 và giá trị lớn nhất là 5

Trong - Arr [] ={10, 12, 3, 2, 5, 18} QStart =2 QEnd =5

Hết -

Giá trị tối thiểu:2

Giá trị tối đa:18

Giải thích - Trong các câu truy vấn trên, chỉ mục bắt đầu là 2 và chỉ mục kết thúc là 5. Giữa hai chỉ mục này, giá trị nhỏ nhất trong Arr là 2 và giá trị lớn nhất là 18

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau -

Trong cách tiếp cận này, chúng tôi sẽ sử dụng cây phân đoạn cho phạm vi lpos đến rpos để tìm các giá trị tối thiểu và tối đa trong phạm vi truy vấn đã cho.

  • Lấy mảng đầu vào Arr [] và truy vấn các chỉ mục QStart và QEnd.

  • Lấy kết quả của giá trị kiểu.

  • Giá trị cấu trúc được sử dụng để lưu trữ giá trị tối thiểu và lớn nhất được tìm thấy trong một mảng bằng cách sử dụng một truy vấn nhất định.

  • Giá trị cấu trúc được sử dụng để lưu trữ giá trị tối thiểu và lớn nhất được tìm thấy trong một mảng bằng cách sử dụng một truy vấn nhất định.

  • Hàm minMax (struct value * root1, int num, int qStart1, int qEnd1) nhận chỉ mục truy vấn và tìm giá trị tối thiểu và tối đa trong một mảng giữa phạm vi chỉ mục qStart1 và qEnd1.

  • Kiểm tra xem (qStart1 <0 HOẶC qEnd1> num-1 HOẶC qStart1> qEnd1). Nếu đúng thì phạm vi đầu vào trong truy vấn không hợp lệ.

  • Nếu không, hãy gọi minmaxFind (root1, 0, num-1, qStart1, qEnd1, 0).

  • Hàm minmaxFind (struct value * root, int startT, int endT, int qStart, int qEnd, int pos) là một hàm đệ quy. Nó cần một con trỏ để phân đoạn gốc cây, chỉ mục bắt đầu và kết thúc của giá trị hiện tại là startT và endT.

  • Nó cũng có chỉ mục bắt đầu và kết thúc trong phạm vi truy vấn. Chỉ mục hiện tại của giá trị trong cây phân đoạn có vị trí chỉ mục.

  • Nếu (qStart <=startT) VÀ nếu (qEnd> =endT) thì đoạn giá trị hiện tại là một phần của dải ô đã cho. Vì vậy, hãy trả về giá trị tối thiểu và tối đa trong giá trị đó.

  • Nếu nó nằm ngoài phạm vi thì hãy cập nhật giá trị hiện tại với minVal và maxVal.

  • Nếu phần hiện tại trùng lặp với phạm vi đã cho thì:-

  • Lấy middl =startT + (endT - startT) / 2.

  • Lấy p1 và p2 là 2 * pos + 1 và =2 * pos + 2.

  • Cập nhật lpos dưới dạng lpos =minmaxFind (root, startT, middl, qStart, qEnd, p1) và rpos dưới dạng minmaxFind (root, middl + 1, endT, qStart, qEnd, p2).

  • Đặt temp.minVal tối thiểu là lpos.minVal và rpos.minVal.

  • Đặt temp.maxVal tối đa là lpos.maxVal và rpos.maxVal.

  • Nhiệt độ trở lại.

  • Hàm segmentTree (int arr2 [], int startT2, int endT2, struct value * root2, int pos2) được sử dụng để tạo cây phân đoạn cho mảng arr2 [] với phạm vi chỉ số là startT2 và endT2 và vị trí giá trị hiện tại là pos2.

  • Hàm * createTree (int arr0 [], int num0) được sử dụng để tạo cây phân đoạn từ một mảng arr0 đã cho. Hàm này cấp phát bộ nhớ cho cây phân đoạn và gọi segmentTree () để cấp phát bộ nhớ.

Ví dụ 

#include<bits/stdc++.h>
using namespace std;
struct value{
   int minVal;
   int maxVal;
};
struct value minmaxFind(struct value *root, int startT, int endT, int qStart,
   int qEnd, int pos){
   struct value temp, lpos ,rpos;
   if (qStart <= startT) {
      if( qEnd >= endT)
         { return root[pos]; }
   }
   if (endT < qStart || startT > qEnd) {
      temp.minVal = 9999;
      temp.maxVal = -9999;
      return temp;
   }
   int middl = startT + ( endT - startT )/2;
   int p1=2*pos+1;
   int p2=2*pos+2;
   lpos = minmaxFind(root, startT, middl, qStart, qEnd, p1);
   rpos = minmaxFind(root, middl+1, endT, qStart, qEnd, p2);
   temp.minVal = (lpos.minVal<rpos.minVal) ? lpos.minVal : rpos.minVal ;
   temp.maxVal = (lpos.maxVal>rpos.maxVal) ? lpos.maxVal : rpos.maxVal ;
   return temp;
}
struct value minMax(struct value *root1, int num, int qStart1, int qEnd1){
   struct value temp1;
   if (qStart1 < 0 || qEnd1 > num-1 || qStart1 > qEnd1){
      cout<<"Please enter Valid input!!";
      temp1.minVal = 9999;
      temp1.maxVal = -9999;
      return temp1;
   }
   return minmaxFind(root1, 0, num-1, qStart1, qEnd1, 0);
}
void segmentTree(int arr2[], int startT2, int endT2, struct value *root2, int pos2){ 
   if (startT2 == endT2) { 
      root2[pos2].minVal = arr2[startT2];
      root2[pos2].maxVal = arr2[startT2];
      return ;
   }
   int p1=pos2*2+1;   
   int p2=pos2*2+2;
   int middl2 = startT2+(endT2-startT2)/2;
   segmentTree(arr2, startT2, middl2, root2, p1);
   segmentTree(arr2, middl2+1, endT2, root2, p2);
   root2[pos2].minVal = root2[p1].minVal<root2[p2].minVal ? root2[p1].minVal : root2[p2].minVal;
   root2[pos2].maxVal = root2[p1].maxVal>root2[p2].maxVal ? root2[p1].maxVal : root2[p2].maxVal;
}
struct value *createTree(int arr0[], int num0) { 
   int height = (int)(ceil(log2(num0)));
   int maxS = 2*(int)pow(2, height) - 1;
   struct value *root0 = new struct value[maxS];
   segmentTree(arr0, 0, num0-1, root0, 0);
   return root0;
}
int main() { 
   int Arr[] = { 1, 2, 3, 4, 5 };
   int length = sizeof(Arr)/sizeof(Arr[0]);
   struct value *tree = createTree(Arr, length);
   int QStart = 1;
   int QEnd = 4;
   struct value answer=minMax(tree, length, QStart, QEnd);
   cout<<"Minimum Value : "<<answer.minVal<<endl;
   cout<<"Maximum Value : "<<answer.maxVal;
   return 0;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra Kết quả sau 

Minimum Value : 2
Maximum Value : 5