მოცემული დიაპაზონის მნიშვნელობების მასივის ელემენტების თვლის მოთხოვნები


Რთული ტური Hard
ხშირად ეკითხებიან Coursera დე შოუ Google პეუ 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- ს შორის მდებარეობს. ძირითადად, ჩვენ უნდა ვიპოვოთ რიცხვების რიცხვი, რომლებიც მეტია "x" - ზე. და ”y” - ზე ნაკლები რიცხვების რაოდენობა. ჩვენ დავალაგებთ მასივს. ამის მიზეზი ის არის, რომ ჩვენ ვიყენებთ ორობითი ძიების მეთოდს. ასევე ხდება მისი შეცვლა.

მიიღეთ ნომრის ინდექსი y მასივში ორობითი ძიების გამოყენებით. ორობითი ძიებისას ვცდილობთ მოვძებნოთ ინდექსი, რომელზეც y იმყოფება. ჩვენ ვაგრძელებთ მარყუჟს მანამ, სანამ დაბალი მნიშვნელობა არ იქნება ნაკლები ან ტოლი მაღალი მნიშვნელობის. ჩვეულებრივ დაბალია მე –0 ინდექსი, ხოლო მაღალი არის მასივის ბოლო ინდექსი, რადგან ჩვენ ვაკეთებთ ორობით ძიებას მასივის ინდექსებზე. ორობითი ძიების გამოყენება საშუალებას გვაძლევს ვუპასუხოთ მასივის ელემენტების თვლებით მოცემულ დიაპაზონში მნიშვნელობებით ლოგარითმული დროის სირთულეში თითოეული მოთხოვნისთვის.

მივიღებთ დაბალი და მაღალი მნიშვნელობის შუაგულს და ვამოწმებთ არის თუ არა მასივი [შუა] ელემენტი x –ზე მეტია? თუ ეს სიმართლეა, განაახლეთ მაღალი მნიშვნელობის 1-ის შუა რიცხვამდე. სხვა შემთხვევაში განაახლეთ დაბალი + 1-ის შუა რიცხვამდე. იგივე უნდა იქნას გამოყენებული y ელემენტთან. ამ შემთხვევაში, ჩვენ ვიხილავთ უფრო მეტ ინდექსს და მასივის შემოწმების ნაცვლად, [y] უფრო მეტია, ვიდრე y ტოლი. შემდეგ შეამოწმეთ, არის თუ არა მასივი [mid] ნაკლებია, ვიდრე 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

სირთულის ანალიზი

დროის სირთულე

თითოეული მოთხოვნის გაშვების დრო იქნება O (შესვლა n) და მასივის დასალაგებლად ერთხელ იქნება O (n log n).

სივრცის სირთულე

O (n) სადაც "ნ" არის მასივის ელემენტების რაოდენობა. სივრცე, რომელიც ჩვენ განვიხილეთ, არის მასივის დახარისხების დროს მიღებული სივრცის გამო. შეყვანის შესანახად საჭირო სივრცე არ არის გათვალისწინებული ”მასივის ელემენტების დათვლის მოთხოვნები მოცემულ დიაპაზონში მნიშვნელობებით”.