दिइएको दायरामा मानको साथ एर्रे एलिमेन्ट्सको गणनाको लागि प्रश्नहरू


कठिनाई तह हार्ड
बारम्बार सोधिन्छ Coursera डे श गुगल PayU स्नैपडल टाइम्स इन्टरनेट याहू
एरे बिट्स प्रश्न समस्या

समस्या वक्तव्य

समस्या "दिइएको दायरामा मानको साथ एर्रे एलिमेन्ट्सको गणनाको लागि प्रश्नहरू" भन्छन् कि तपाईंसँग एक छ पूर्णांक array र दुई नम्बर x र y। समस्या कथनले एरेमा रहेको नम्बरहरूको गणना पत्ता लगाउन अनुरोध गर्दछ जुन दिइएको x र y को बीचमा छ।

उदाहरणका

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

स्पष्टीकरण

किनकि त्यहाँ एर्रेमा elements तत्वहरू उपस्थित छन्, त्यो २,,,,, र that र २ र between बीचमा समावेश छ।

दिइएको दायरामा मानको साथ एर्रे एलिमेन्ट्सको गणनाको लागि प्रश्नहरू

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

स्पष्टीकरण

किनकि त्यहाँ एर्रेमा elements तत्वहरू उपस्थित छन्, ती 3,,, र १० हुन्, जुन and र १० समावेशी बीचमा पर्दछ।

अल्गोरिदम

  1. सर्ट एर्रे।
  2. Y y एलिमेन्टको एर्रेको ठूलो सूचकांक बाइनरी खोज प्रयोग गरेर फेला पार्नुहोस्, ठूलो अनुक्रमणिका फिर्ता गर्नुहोस्।
  3. बाइनरी खोज प्रयोग गरेर एलिमेन्ट x को एरेको सानो सूचकांक फेला पार्नुहोस्, सानो सूचकांक फिर्ता गर्नुहोस्।
  4. ठूलो अनुक्रमणिका र सानो अनुक्रमणिका र प्लस १ बीच भिन्नता फिर्ता गर्नुहोस्।

स्पष्टीकरण

हामीले एउटा पूर्णा ar्क एरे र दुई नम्बर x र y दिएका छौं। हामीले दिइएको एर्रेमा रहेको कुल संख्या पत्ता लगाउन सोध्यौं जुन दिइएको x र y को बीचमा छ। साधारणतया, हामीले "x" भन्दा ठूलो नम्बरहरूको गणना पत्ता लगाउनुपर्दछ। र "y" भन्दा सानो संख्याको गणना। हामी एर्रे क्रमबद्ध गर्दैछौं। यसको पछाडिको कारण यो हो कि हामी बाइनरी खोज विधि प्रयोग गर्ने छौं। त्यो पनि परिमार्जन भइरहेको छ।

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

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

दुवै सूचकहरू ठूला र सानोका रूपमा प्राप्त गर्नुहोस्, र ती मध्ये भिन्नता फर्काउनुहोस् र यसलाई १ थप्नुहोस्। यो हाम्रो आवश्यक उत्तर हो जुन फिर्ता भएको छ। याद गर्नुहोस्, हामी दिइएको दायरामा मानको साथ एर्रे एलिमेन्ट्सको गणनाको लागि प्रश्नहरूको उत्तर दिन चाहन्थ्यौं।

कोड

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 (लग एन) र एर्रे क्रमबद्ध गर्न को लागी एक पटक हुनेछ O (n log n).

ठाउँ जटिलता

ऊ) जहाँ "N" एर्रेमा एलिमेन्ट्सको संख्या हो। स्पेस जुन हामीले हेरेका छौँ किनकी स्थानको कारण छ एरे क्रमबद्ध गर्ने क्रममा। इनपुट भण्डारण गर्नका लागि आवश्यक स्थान "समस्याको दायरामा मानका साथ एर्रे एलिमेन्ट्सको गन्तीका लागि प्रश्नहरू" मा मानिदैन।