આપેલ શ્રેણીના મૂલ્યોવાળા એરે તત્વોની ગણતરી માટે પ્રશ્નો


મુશ્કેલી સ્તર હાર્ડ
વારંવાર પૂછવામાં આવે છે Coursera ડીઇ શw Google પે સ્નેપડીલ ટાઇમ્સ ઇન્ટરનેટ યાહૂ
અરે બિટ્સ ક્વેરી સમસ્યા

સમસ્યા નિવેદન

સમસ્યા "આપેલ શ્રેણીના મૂલ્યોવાળા એરે તત્વોની ગણતરીઓ માટે ક્વેરીઝ" જણાવે છે કે તમારી પાસે પૂર્ણાંક એરે અને બે નંબર એક્સ અને વાય. સમસ્યા નિવેદન એરેમાં હાજર નંબરોની ગણતરી શોધવા માટે પૂછે છે જે આપેલ 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” કરતા ઓછી સંખ્યાઓની ગણતરી. આપણે એરેને સingર્ટ કરીશું. તેની પાછળનું કારણ એ છે કે આપણે દ્વિસંગી શોધ પદ્ધતિનો ઉપયોગ કરીશું. તેમાં પણ ફેરફાર કરવામાં આવી રહ્યા છે.

નંબરની અનુક્રમણિકા મેળવો y દ્વિસંગી શોધનો ઉપયોગ કરીને એરેમાં. દ્વિસંગી શોધમાં, અમે અનુક્રમણિકા શોધવાનો પ્રયાસ કરીએ છીએ કે જેના પર y હાજર છે. જ્યાં સુધી નીચી કિંમત ઉચ્ચ મૂલ્ય કરતા ઓછી અથવા તેના બરાબર ન થાય ત્યાં સુધી અમે લૂપ ચાલુ રાખીએ છીએ. સામાન્ય રીતે નીચી એ 0 મી અનુક્રમણિકા હોય છે અને એરેનો છેલ્લો અનુક્રમણિકા વધારે હોય છે કારણ કે આપણે એરે સૂચકાંકો પર બાઈનરી શોધ કરી રહ્યા છીએ. દ્વિસંગી શોધનો ઉપયોગ અમને દરેક ક્વેરી માટે લarગાર્થોમિક સમય જટિલતામાં આપવામાં આવતી શ્રેણીના મૂલ્યોવાળા એરે તત્વોની ગણતરીઓના પ્રશ્નોના જવાબને મંજૂરી આપે છે.

અમને નીચા અને ઉચ્ચ મૂલ્યની મધ્યમાં મળશે, અને એરે [મધ્ય] પર હાજર તત્વ, x ની બરાબર કરતાં વધુ છે કે કેમ તે તપાસો. જો આ સાચું છે, તો ઉચ્ચ-મધ્યમાં 1 ની કિંમત અપડેટ કરો. અન્યથા નીચાથી મધ્ય +1 ની કિંમત અપડેટ કરો. તત્વ વાય સાથે સમાન લાગુ પાડવાનું છે. પરંતુ તે કિસ્સામાં, આપણે વધારે અનુક્રમણિકા શોધીશું, અને એરે તપાસવાને બદલે [મધ્ય] y બરાબર કરતા વધારે છે. પછી એરે [મધ્ય] વાય બરાબર કરતા ઓછું છે કે કેમ તે તપાસવાનું ચાલુ રાખો, અને નીચાથી મધ્ય +1 ની કિંમત અને ઉચ્ચથી મધ્ય -1 ની કિંમત અપડેટ કરો.

બંને સૂચકાંકોને મોટા અને નાના તરીકે મેળવો અને તેમાંનો તફાવત પાછો ફરો અને તેમાં 1 ઉમેરો. આ આપણો જરૂરી જવાબ હશે જે પાછો ફર્યો છે. યાદ રાખો, અમે આપેલ શ્રેણીના મૂલ્યોવાળા એરે તત્વોની ગણતરીઓ માટેના પ્રશ્નોના જવાબો આપવા માગતા હતા.

કોડ

આપેલ શ્રેણીમાં એરે તત્વોની ગણતરી શોધવા માટે સી ++ કોડ

#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

જટિલતા વિશ્લેષણ

સમય જટિલતા

દરેક ક્વેરી ચલાવવાનો સમય હશે ઓ (લોગ એન) અને એરેને સingર્ટ કરવા માટે એકવાર હશે ઓ (એન લ logગ એન).

અવકાશ જટિલતા

ઓ (એન) જ્યાં “એન” એરેમાં તત્વોની સંખ્યા છે. એરે જે સ weર્ટ કરતી વખતે લેવાયેલી જગ્યાને કારણે આપણે ધ્યાનમાં લીધી છે. ઇનપુટ સ્ટોર કરવા માટે જરૂરી જગ્યાને “આપેલ શ્રેણીના મૂલ્યોવાળા એરે તત્વોની ગણતરી માટેની ક્વેરીઝ” સમસ્યામાં ધ્યાનમાં લેવામાં આવતી નથી.