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


Ниво тешкоће Тежак
Често питани у Цоурсера ДЕ Схав гоогле ПаиУ Снапдеал Тимес Интернет иахоо
Ред Битс Куери Проблем

Изјава о проблему  

Проблем „Упити за бројање елемената низа са вредностима у датом опсегу“ наводи да имате цео број поредак и два броја к и и. Изјава о проблему тражи да се сазна број бројева присутних у низу који се налази између задатих к и и.

Пример  

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. Пронађи мањи индекс низа елемента к помоћу бинарне претраге, врати мањи индекс.
  4. Врати разлику између већег и мањег индекса и плус 1.

Објашњење  

Дали смо целобројни низ и два броја к и и. Затражили смо да сазнамо укупне бројеве присутне у датом низу који се налази између задатих к и и. У основи, морамо пронаћи број бројева већи од „к“. И бројање бројева мањих од „и“. Разврстаћемо низ. Разлог томе је што ћемо користити бинарни метод претраживања. То се такође модификује.

Види такође
Уклоните минималан број елемената таквих да у оба поља не постоји заједнички елемент

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

Добићемо средину мале и високе вредности и проверити да ли је елемент присутан у низу [мид] већи од једнаког к. Ако је ово тачно, ажурирајте вредност високе на средину 1. Иначе ажурирајте вредност од најниже до средње + 1. Исто се примењује и са елементом и. Али у том случају ћемо пронаћи већи индекс и уместо да проверимо низ [мид] је већи од једнак и. Затим наставите да проверавате да ли је низ [мид] мањи од једнаког и, и ажурирајте вредност од лов до мид + 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

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

Сложеност времена

Време за покретање сваког упита ће бити О (лог н) а за сортирање низа једном биће О (н лог н).

Види такође
Како проверити да ли су два дата скупа дисјунктна?

Сложеност простора

Он) где „Н“ је број елемената у низу. Простор који смо узели у обзир је због простора заузетог током сортирања низа. Простор потребан за чување улазних података не узима се у обзир у проблему „Упити за бројање елемената низа са вредностима у датом опсегу“.