פֿראגן פֿאַר קאַונץ פון מענגע עלעמענטן מיט וואַלועס אין געגעבן קייט


שוועריקייט לעוועל שווער
אָפט געבעטן אין קאָורסעראַ DE שאָ גוגל PayU סנאַפּדעאַל Times אינטערנעט יאַהאָאָ
מענגע ביץ אָנפֿרעג פּראָבלעם

פּראָבלעם סטאַטעמענט

די פּראָבלעם "פֿראגן פֿאַר קאַונץ פון מענגע עלעמענטן מיט וואַלועס אין געגעבן קייט" שטאַטן אַז איר האָבן אַן ינטעגער מענגע און צוויי נומער 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. מיר פאָרזעצן די שלייף ביז די ווערט פון נידעריק איז ווייניקער ווי אָדער גלייַך צו די ווערט פון הויך. יוזשאַוואַלי נידעריק איז די 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

Java פּראָגראַם צו געפֿינען די ציילן פון מענגע עלעמענטן אין אַ געגעבן קייט

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 קלאָץ n).

ספעיס קאַמפּלעקסיטי

אָ (N) ווו “N” איז די נומער פון עלעמענטן אין דער מענגע. די פּלאַץ וואָס מיר באַטראַכטן איז ווייַל פון די פּלאַץ גענומען בעשאַס די סאָרטירונג פון די מענגע. די פּלאַץ פארלאנגט פֿאַר סטאָרינג די ינפּוט איז נישט באַטראַכט אין די "פֿראגן פֿאַר קאַונץ פון מענגע עלעמענטן מיט וואַלועס אין אַ געגעבן קייט" פּראָבלעם.