Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ प्रोग्राम में L-वें और R-वें सबसे छोटे नंबर के बीच निरपेक्ष अंतर के लिए क्वेरीज

समस्या विवरण

इस समस्या में, हमें आकार n का एक ऐरे arr[] और Q क्वेरीज दी गई हैं जिनमें प्रत्येक में 2 मान L और R होते हैं। हमारा कार्य L-वें सबसे छोटे नंबर और R-वें सबसे छोटे नंबर के बीच निरपेक्ष अंतर वापस करने के लिए क्वेरीज को हल करने का प्रोग्राम बनाना है।

समस्या विवरण - प्रत्येक क्वेरी को हल करने के लिए, हमें Lवें सबसे छोटे और Rवें सबसे छोटे नंबर का इंडेक्स ढूंढना होगा। और इन इंडेक्स के बीच अंतर ढूंढना होगा।

उदाहरण

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

आउटपुट

1 2

व्याख्या

{2, 4} के लिए: 2वां सबसे छोटा तत्व 2 है जिसका इंडेक्स 4 है
4वां सबसे छोटा तत्व 5 है जिसका इंडेक्स 3 है
अंतर = 4 - 3 = 1

{1, 5} के लिए: सबसे छोटा तत्व 1 है जिसका इंडेक्स 2 है
5वां सबसे छोटा तत्व 8 है जिसका इंडेक्स 0 है
अंतर = 2 - 0 = 2

हल करने का दृष्टिकोण

समस्या को हल करने के लिए, हम एक पेयर बनाएंगे जो ऐरे तत्वों के इंडेक्स और मान को संग्रहीत करेगा। और प्रत्येक क्वेरी के L और R मानों के लिए i-वां सबसे छोटा तत्व ढूंढेंगे। फिर उनके इंडेक्स के निरपेक्ष अंतर को प्रिंट करेंगे।

उदाहरण 1: पेयर डेटा स्ट्रक्चर का उपयोग करके

#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;
}

आउटपुट

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

उदाहरण 2: पेयर के बिना दृष्टिकोण

#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;
}

आउटपुट

For Query 1: Difference is 1
For Query 2: Difference is 2
  1. - C++ में डिक्लेरेशन और डेफिनिशन में क्या अंतर है?

    C++ में डिक्लेरेशन और डेफिनिशन अक्सर भ्रमित होते हैं। डिक्लेरेशन का अर्थ है (C में) कि आप कंपाइलर को किसी वेरिएबल, या यूजर-डिफाइंड टाइप या फंक्शन के टाइप, साइज और फंक्शन डिक्लेरेशन के मामले में उसके पैरामीटर्स के टाइप और साइज के बारे में बता रहे हैं। डिक्लेरेशन के मामले में किसी भी वेरिएबल के लिए म

  1. - C# में दो पूर्णांकों का शेषफल (Remainder) निकालना

    C# में दो पूर्णांकों का शेषफल (remainder) निकालने के लिए मॉड्यूलो ऑपरेटर % का उपयोग किया जाता है। यह प्रोग्राम विभाजन से पहले दो वैधता जांच करता है: भाजक (divisor) शून्य नहीं होना चाहिए, और भाज्य (dividend) भाजक से छोटा नहीं होना चाहिए। पूर्ण कोड using System; namespace Program { class Demo

  1. - जावा में सरणी में सबसे बड़ी और सबसे छोटी अभाज्य संख्या के बीच अंतर

    समस्या कथन पूर्णांकों की एक दी गई सरणी जहां सभी तत्व 1000000 से कम हैं। सरणी में सबसे बड़ी और सबसे छोटी अभाज्य संख्या के बीच का अंतर ज्ञात करें। उदाहरण सरणी: [ 1, 2, 3, 4, 5 ] सबसे बड़ी अभाज्य संख्या = 5 सबसे छोटी अभाज्य संख्या = 2 अंतर = 5 - 2 = 3 समाधान एराटोस्थनीज की छलनी (Sieve of Eratosthe