Truy vấn để trả về sự khác biệt tuyệt đối giữa số nhỏ nhất thứ L và số nhỏ nhất thứ R trong Chương trình C ++

Trong bài toán này, chúng ta được cung cấp một mảng arr [] có kích thước n và Q truy vấn, mỗi truy vấn gồm 2 giá trị L và R. Nhiệm vụ của chúng ta là tạo một chương trình giải quyết các truy vấn để trả về sự khác biệt tuyệt đối giữa số nhỏ nhất thứ L và Số nhỏ nhất thứ R.

Mô tả sự cố - Để giải từng câu truy vấn, ta cần tìm chỉ số của số nhỏ nhất thứ L và số nhỏ nhất thứ R. Và tìm sự khác biệt giữa các chỉ số này.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào

arr[] = {8, 4, 1, 5, 2} Q = 2 Queries[][] = {{2, 4}, {1, 5}}

Đầu ra

1 2

Giải thích

For {2, 4}: 2nd smallest element is 2 whose index is 4
4th smallest element is 5 whose index is 3 Difference = 4 - 3 = 1
For {1, 5} Smallest element is 1 whose index is 2
5th smallest element is 8 whose index is 0 Difference = 2 - 0 = 2

Phương pháp tiếp cận giải pháp

Để giải quyết vấn đề, chúng ta sẽ tạo một cặp lưu trữ các chỉ số và giá trị của các phần tử mảng. Và tìm phần tử nhỏ nhất thứ i cho cả giá trị L và R của mỗi truy vấn. Sau đó, in sự khác biệt tuyệt đối của các chỉ số của chúng.

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

Ví dụ

#include <bits/stdc++.h>
using namespace std;
void solveAllQueries(int arr[], int n,int Q, int queries[][2] ) {
   pair<int, int> arrayIndex[n];
   for (int i = 0; i < n; i++) {
      arrayIndex[i].first = arr[i];
      arrayIndex[i].second = i;
   }  
   sort(arrayIndex, arrayIndex + n);
   for (int i = 0; i < Q; i++){
      int result = ( abs(arrayIndex[queries[i][0] - 1].second - arrayIndex[queries[i][1] - 1].second) );
      cout<<"For Query "<<(i+1)<<": Difference is "<<result<<endl;
   }
}
int main() {
   int arr[] = { 8, 4, 1, 5, 2 };
   int n = sizeof(arr) / sizeof(arr[0]);
   int Q = 2; int queries[][2] = { { 2, 4 }, { 1, 5 }};
   solveAllQueries(arr, n, Q, queries);
   return 0;
}

Đầu ra

For Query 1: Difference is 1
For Query 2: Difference is 2

Chương trình này sử dụng cấu trúc dữ liệu cặp nhưng có một giải pháp có thể tìm ra sự khác biệt mà không cần sử dụng nó. Đối với điều này, chúng tôi sẽ sử dụng một mảng sẽ lưu trữ các phần tử theo thứ tự tăng dần. Và sau đó tìm phần tử nhỏ nhất thứ i cho cả hai giá trị của L và R cho mỗi truy vấn. Sau đó, tìm sự khác biệt của các chỉ số của chúng.

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

Ví dụ

#include <bits/stdc++.h>
using namespace std;
int searchEle(int arr[], int ele, int n){
    for(int i = 0; i < n; i++)
   if(arr[i] == ele)
      return i;
      return -1;
}
int findDifference(int arr[], int minArray[], int n, int L, int R){
   int Lele = minArray[L-1];
   int Rele = minArray[R-1];
   int index1 = searchEle(arr, Lele, n);
   int index2 = searchEle(arr, Rele, n);
   return abs(index1 - index2);
 }
void solveAllQueries(int arr[], int n,int Q, int queries[][2] ) {
   int minArray[n];
   for (int i = 0; i < n; i++)
   minArray[i] = arr[i];
   sort(minArray, minArray + n);
   for(int i = 0; i < Q; i++){
      cout<<"For Query "<<(i+1)<<": Difference is "<<findDifference(arr, minArray, n,       queries[i][0], queries[i][1])<<endl;
   }
}
int main() {
   int arr[] = { 8, 4, 1, 5, 2 };
   int n = sizeof(arr) / sizeof(arr[0]);
   int Q = 2; int queries[][2] = { { 2, 4 }, { 1, 5 }};
   solveAllQueries(arr, n, Q, queries); return 0;
}

Đầu ra

For Query 1: Difference is 1
For Query 2: Difference is 2