Барања за броење на елементи во низата со вредности во даден опсег


Ниво на тешкотија Тешко
Често прашувано во 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“. Beе ја сортираме низата. Причината што стои зад тоа е дека ние ќе користиме бинарен метод за пребарување. Исто така се менува.

Добијте го индексот на бројот y во низата со користење на бинарно пребарување. Во бинарното пребарување, се обидуваме да го најдеме индексот на кој е присутен y. Ние ја продолжуваме јамката додека вредноста на ниската не е помала или еднаква на вредноста на високото. Обично низок е 0-от индекс, а висок е последниот индекс на низата затоа што правиме бинарно пребарување преку индексите на низата. Користењето бинарно пребарување ни овозможува да одговориме на пребарувања за броење елементи на низа со вредности во даден опсег во логаритамска сложеност на времето за секое пребарување.

Getе ја добиеме средината на ниската и високата вредност и ќе провериме дали елементот присутен во низата [средина] е поголем од еднаков на 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

Анализа на сложеност

Временска комплексност

Времето за извршување на секое барање ќе биде О (дневник н) и за сортирање на низата еднаш ќе биде О (н дневник н).

Комплексноста на просторот

Тој) каде „Н“ е бројот на елементи во низата. Просторот што го разгледавме е заради просторот зафатен при сортирање на низата. Просторот потребен за зачувување на влезот не се разгледува во проблемот „Барања за броење елементи на низа со вредности во даден опсег“.