Запыты падлікаў элементаў масіва са значэннямі ў зададзеным дыяпазоне


Узровень складанасці Жорсткі
Часта пытаюцца ў Coursera DE Шоу Google PayU Snapdeal Times Інтэрнэт Yahoo
масіў біты Задача запыту

Пастаноўка праблемы

Праблема "Запыты падлікаў элементаў масіва са значэннямі ў зададзеным дыяпазоне" абвяшчае, што ў вас ёсць цэлае масіў і два нумары х і у. Пастаноўка задачы просіць высветліць колькасць лікаў у масіве, якое знаходзіцца паміж дадзенымі х і у.

Прыклад

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. Мы папрасілі высветліць агульную колькасць прысутных у дадзеным масіве, які знаходзіцца паміж дадзенымі х і у. У асноўным мы павінны знайсці колькасць лікаў, большае за "х". І падлік лікаў, меншых за "у". Мы будзем сартаваць масіў. Прычына гэтага заключаецца ў тым, што мы збіраемся выкарыстоўваць бінарны метад пошуку. Гэта таксама мадыфікуецца.

Атрымаць індэкс ліку y у масіве з дапамогай бінарнага пошуку. У двайковым пошуку мы спрабуем знайсці індэкс, пры якім прысутнічае y. Мы працягваем цыкл, пакуль значэнне нізкага не будзе менш або роўна значэнню высокага. Звычайна нізкі - гэта 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 (часопіс n) і для сартавання масіва адзін раз будзе O (n log n).

Касмічная складанасць

Аб (п) дзе "П" - колькасць элементаў у масіве. Прастора, якую мы разгледзелі, звязана з прасторай, занятай падчас сартавання масіва. Прастора, неабходная для захоўвання ўваходных дадзеных, не разглядаецца ў задачы "Запыты на падлік элементаў масіва са значэннямі ў зададзеным дыяпазоне".