दिए गए रेंज में मूल्यों के साथ सरणी तत्वों की गिनती के लिए प्रश्न


कठिनाई स्तर कठिन
में अक्सर पूछा Coursera डीई शॉ गूगल PayU स्नैपडील टाइम्स इंटरनेट याहू
ऐरे बिट्स क्वेरी की समस्या

समस्या का विवरण

समस्या "दिए गए रेंज में मूल्यों के साथ सरणी तत्वों की संख्या के लिए प्रश्न" बताता है कि आपके पास ए पूर्णांक सरणी और दो नंबर x और y। समस्या कथन सरणी में मौजूद संख्याओं की गिनती का पता लगाने के लिए कहता है जो दिए गए x और y के बीच स्थित है।

उदाहरण

arr[]={2,4,6,8,1,10}
x = 2, y = 8
4

व्याख्या

क्योंकि एक सरणी में 4 तत्व मौजूद हैं, जो कि 2, 4, 6, और 8 हैं जो कि 2 और 8 के बीच में सम्मिलित हैं।

दिए गए रेंज में मूल्यों के साथ सरणी तत्वों की गिनती के लिए प्रश्न

arr[]={2,4,6,8,1,10}
x = 5, y = 10
3

व्याख्या

क्योंकि एक सरणी में 3 तत्व मौजूद हैं, जो कि 6, 8 और 10 हैं, जो कि 5 और 10 के बीच समावेशी है।

कलन विधि

  1. तरह सरणी।
  2. द्विआधारी खोज का उपयोग करके तत्व वाई के सरणी के अधिक से अधिक सूचकांक का पता लगाएं, अधिक से अधिक सूचकांक लौटाएं।
  3. बाइनरी खोज का उपयोग करके तत्व x के सरणी के छोटे सूचकांक का पता लगाएं, छोटे सूचकांक को वापस करें।
  4. अधिक इंडेक्स और छोटे इंडेक्स और प्लस 1 के बीच अंतर लौटाएं।

व्याख्या

हमने एक पूर्णांक सरणी और दो नंबर x और y दिए हैं। हमने किसी दिए गए सरणी में मौजूद कुल संख्याओं का पता लगाने के लिए कहा है जो दिए गए x और y के बीच स्थित है। मूल रूप से, हमें "x" से अधिक संख्याओं की संख्या ज्ञात करनी होगी। और संख्याओं की संख्या "y" से छोटी है। हम सरणी को सॉर्ट करेंगे। इसके पीछे कारण यह है कि हम एक द्विआधारी खोज विधि का उपयोग करने जा रहे हैं। वह भी संशोधित किया जा रहा है।

संख्या का सूचकांक प्राप्त करें y सरणी में बाइनरी खोज का उपयोग करके। बाइनरी खोज में, हम उस सूचकांक को खोजने की कोशिश करते हैं जिस पर y मौजूद है। हम लूप को तब तक जारी रखते हैं जब तक कि कम का मान उच्च के मान से कम या उसके बराबर न हो। आमतौर पर कम 0 वां सूचकांक है और उच्च सरणी का अंतिम सूचकांक है क्योंकि हम सरणी सूचकांकों पर एक द्विआधारी खोज कर रहे हैं। द्विआधारी खोज का उपयोग करने से हमें प्रत्येक क्वेरी के लिए लघुगणक समय जटिलता में दिए गए रेंज में मूल्यों के साथ सरणी तत्वों की गणना के लिए क्वेरी का जवाब देने की अनुमति मिलती है।

हम निम्न और उच्च मूल्य के मध्य को प्राप्त करेंगे, और जांचेंगे कि क्या सरणी में मौजूद तत्व [मध्य] x के बराबर है। यदि यह सच है, तो उच्च के मूल्य को मध्य -1 में अपडेट करें। कम से कम के मूल्य को मध्य + 1 में अपडेट करें। वही तत्व y के साथ लागू किया जाना है। लेकिन उस स्थिति में, हम अधिक से अधिक सूचकांक ढूंढेंगे, और सरणी की जांच करने के बजाय [मध्य] y के बराबर है। फिर जाँचते रहें कि क्या सरणी [मध्य] y के बराबर कम है, और निम्न के मान को मध्य + 1 और उच्च के मान को मध्य -1 तक अद्यतन करें।

दोनों सूचकांकों को अधिक से अधिक और छोटे रूप में प्राप्त करें, और उनमें से अंतर लौटाएं और इसमें 1 जोड़ें। यह हमारा आवश्यक उत्तर होगा जो लौटा दिया गया है। याद रखें, हम दिए गए रेंज में मूल्यों के साथ सरणी तत्वों की गिनती के लिए प्रश्नों का उत्तर देना चाहते थे।

कोड

किसी दिए गए सीमा के भीतर सरणी तत्वों की गिनती खोजने के लिए C ++ कोड

#include<iostream>
#include<algorithm>

using namespace std;

int smallerElement(int arr[], int n, int x)
{
    int low = 0, high = n - 1;
    while (low <= high)
    {
        int mid = (low + high) / 2;
        if (arr[mid] >= x)
            high = mid - 1;
        else
            low = mid + 1;
    }
    return low;
}
int greaterElement(int arr[], int n, int y)
{
    int low = 0, high = n - 1;
    while (low <= high)
    {
        int mid = (low + high) / 2;
        if (arr[mid] <= y)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return high;
}
int countInRange(int arr[], int n, int x, int y)
{
    int count = 0;
    count = greaterElement(arr, n, y) - smallerElement(arr, n, x) + 1;
    return count;
}
int main()
{
    int arr[] = {2,4,6,8,1,10 };
    int n = sizeof(arr) / sizeof(arr[0]);

    sort(arr, arr + n);

    int i = 2, j = 8;
    cout << countInRange(arr, n, i, j) << endl;

    i = 5, j = 10;
    cout << countInRange(arr, n, i, j) << endl;
    return 0;
}
4
3

किसी दिए गए रेंज के भीतर सरणी तत्वों की गिनती खोजने के लिए जावा प्रोग्राम

import java.io.*;
import java.util.Arrays;

class NumberOfElements
{
    private static int countInRange(int arr[], int n, int x, int y)
    {
        int count = 0;
        count = greaterElement(arr, n, y) -
                smallerElement(arr, n, x) + 1;
        return count;
    }
    
    private static int smallerElement(int arr[], int n, int x)
    {
        int low = 0, high = n - 1;
        while (low <= high)
        {
            int mid = (low + high) / 2;
            if (arr[mid] >= x)
                high = mid - 1;
            else
                low = mid + 1;
        }
        return low;
    }
    
    private static int greaterElement(int arr[], int n, int y)
    {
        int low = 0, high = n - 1;
        while (low <= high)
        {
            int mid = (low + high) / 2;
            if (arr[mid] <= y)
                low = mid + 1;
            else
                high = mid - 1;
        }
        return high;
    }

    public static void main (String[] args)
    {
        int arr[] = {2,4,6,8,1,10 };
        int n = arr.length;

        Arrays.sort(arr);

        int x = 2, y = 8;
        System.out.println( countInRange(arr, n, x, y)); ;

        x = 5;
        y = 10;
        System.out.println( countInRange(arr, n, x, y));
    }
}
4
3

जटिलता विश्लेषण

समय जटिलता

प्रत्येक क्वेरी को चलाने का समय होगा O (लॉग एन) और सरणी को एक बार छाँटने के लिए होगा ओ (एन लॉग एन).

अंतरिक्ष जटिलता

पर) जहां "N" सरणी में तत्वों की संख्या है। अंतरिक्ष जिसे हमने माना है वह सरणी की छंटाई के दौरान लिए गए स्थान के कारण है। इनपुट को संग्रहीत करने के लिए आवश्यक स्थान को "श्रेणी में दिए गए मानों के साथ सरणी तत्वों की गणना के लिए प्रश्न" में नहीं माना जाता है।