Заявки за брой елементи на масива със стойности в даден диапазон  


Ниво на трудност Трудно
Често задавани в Coursera DE Шоу Google PayU Snapdeal Times Интернет Yahoo
Array Bits Задача за заявка

Декларация за проблема  

Проблемът „Заявки за брой елементи на масива със стойности в даден диапазон“ гласи, че имате цяло число масив и две числа 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. По принцип трябва да намерим броя на числата, по-големи от „х“. И броят на числата, по-малки от „y“. Ще сортираме масива. Причината за това е, че ще използваме двоичен метод за търсене. Това също се модифицира.

Вижте също
Премахнете минимален брой елементи, така че да няма общ елемент и в двата масива

Вземете индекса на числото y в масива с помощта на двоично търсене. При двоичното търсене се опитваме да намерим индекса, в който присъства y. Продължаваме цикъла, докато стойността на low е по-малка или равна на стойността на high. Обикновено ниският е 0-ият индекс, а високият е последният индекс на масива, защото правим двоично търсене на индексите на масива. Използването на двоично търсене ни позволява да отговаряме на заявки за броя на елементите на масива със стойности в даден диапазон в логаритмична времева сложност за всяка заявка.

Ще получим средата на ниската и високата стойност и ще проверим дали елементът, присъстващ в масива [mid], е по-голям от равен на x. Ако това е вярно, актуализирайте стойността на high до средата на 1. В противен случай актуализирайте стойността от ниска до средна + 1. Същото трябва да се приложи и с елемента y. Но в този случай ще намерим по-големия индекс и вместо да проверяваме масива [mid] е по-голям от равен на y. След това продължете да проверявате дали масивът [mid] е по-малък от равен на y и актуализирайте стойността от low до mid + 1 и стойност от high до mid-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

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

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

Времето за изпълнение на всяка заявка ще бъде O (log n) и за сортиране на масива веднъж ще бъде O (n log n).

Вижте също
Как да проверя дали два дадени комплекта не са свързани?

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

О (п) където "н" е броят на елементите в масива. Пространството, което разгледахме, се дължи на пространството, заето по време на сортирането на масива. Пространството, необходимо за съхранение на входа, не се разглежда в проблема „Заявки за брой елементи на масива със стойности в даден диапазон“.