በተሰጠው ክልል ውስጥ እሴቶች ያላቸው የበርካታ ድርድር አካላት ብዛት ጥያቄዎች


የችግር ደረጃ ጠንካራ
ውስጥ በተደጋጋሚ ተጠየቀ Coursera ዴ ሻው google PayU Snapdeal ታይምስ በይነመረብ ያሁ
ሰልፍ ቢት የጥያቄ ችግር

የችግሩ መግለጫ

ችግሩ “በተጠቀሰው ክልል ውስጥ ካሉ እሴቶች ጋር ለድርድር አካላት ብዛት ጥያቄዎች” አንድ እንዳለዎት ይገልጻል ኢንቲጀር ደርድር እና ሁለት ቁጥር 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. የሁለትዮሽ ፍለጋን በመጠቀም የ y ንጥል ትልቁን ማውጫ ይፈልጉ ፣ ትልቁን ማውጫ ይመልሱ።
  3. የሁለትዮሽ ፍለጋን በመጠቀም የንጥል x አነስተኛውን ማውጫ ይፈልጉ ፣ ትንሹን መረጃውን ይመልሱ።
  4. በትልቁ መረጃ ጠቋሚ እና በትንሽ ኢንዴክስ እና በተጨማሪ 1 መካከል ያለውን ልዩነት ይመልሱ።

ማስረጃ

የኢቲጀር ድርድር እና ሁለት ቁጥሮች x እና y ሰጥተናል ፡፡ በተሰጠው x እና y መካከል ባለው በተወሰነ ድርድር ውስጥ የሚገኙትን ጠቅላላ ቁጥሮች ለማወቅ ጠይቀናል። በመሠረቱ ፣ ከ “x” የሚበልጡ የቁጥሮችን ብዛት መፈለግ አለብን። እና ከ “y” ያነሱ ቁጥሮች ብዛት። ድርድርን እየደረደርን እንሆናለን። ከጀርባው ያለው ምክንያት የሁለትዮሽ ፍለጋ ዘዴን የምንጠቀም መሆኑ ነው ፡፡ ያ ደግሞ እየተሻሻለ ነው ፡፡

የቁጥሩን ማውጫ ያግኙ y የሁለትዮሽ ፍለጋን በመጠቀም በድርድሩ ውስጥ በሁለትዮሽ ፍለጋ ውስጥ y የሚገኝበትን መረጃ ጠቋሚ ለማግኘት እንሞክራለን ፡፡ የዝቅተኛ እሴት ከከፍተኛው እሴት በታች ወይም እኩል እስኪሆን ድረስ ቀለበቱን እንቀጥላለን። በድርድር ኢንዴክሶች ላይ የሁለትዮሽ ፍለጋን ስለምናደርግ ብዙውን ጊዜ ዝቅተኛው የ 0 ኛ መረጃ ጠቋሚ ሲሆን ከፍተኛ ደግሞ የድርድሩ የመጨረሻ መረጃ ጠቋሚ ነው። የሁለትዮሽ ፍለጋን በመጠቀም ለእያንዳንዱ ጥያቄ በሎጋሪዝም የጊዜ ውስብስብነት ውስጥ በተወሰነ ክልል ውስጥ ያሉ እሴቶች ያላቸው የበርካታ አካላት ብዛት ጥያቄዎችን እንድንመልስ ያስችለናል።

የዝቅተኛውን እና የከፍተኛውን እሴት እናገኛለን ፣ እና በድርድር [መካከለኛ] ላይ ያለው ንጥረ ነገር ከ x ጋር እኩል መሆኑን ያረጋግጡ። ይህ እውነት ከሆነ ከዚያ ከከፍተኛው እስከ አጋማሽ ያለውን እሴት ያዘምኑ። ሌላ ከዝቅተኛ እስከ አጋማሽ + 1 ያለውን እሴት ያዘምኑ። ተመሳሳይ ከሆነው ንጥረ-ነገር ጋር ሊተገበር ነው 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

ውስብስብነት ትንተና

የጊዜ ውስብስብነት

እያንዳንዱን ጥያቄ ለማስኬድ ጊዜ ይሆናል ኦ (ምዝግብ ማስታወሻ n) እና አንድ ጊዜ ድርድርን ለመደርደር ይሆናል ኦ (n log n).

የቦታ ውስብስብነት

ሆይ (n) የት “N” በድርድሩ ውስጥ ያሉት ንጥረ ነገሮች ብዛት ነው። የተመለከትንበት ቦታ ድርድሩ በሚደረደርበት ጊዜ በተወሰደው ቦታ ምክንያት ነው ፡፡ ግቤቱን ለማከማቸት የሚያስፈልገው ቦታ “በተሰጠው ክልል ውስጥ እሴቶች ካሉባቸው የድርጅት አባሎች ብዛት ጥያቄዎች” ውስጥ አይታሰብም።