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


Ниво на трудност Трудно
Често задавани в Coursera DE Шоу Google PayU Snapdeal Times Internet 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).

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

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