Verilən aralığında dəyərləri olan sıra elementlərinin sayı üçün sorğular

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur Coursera DE Şou google PayU Snapdeal Times İnternet Yahoo
Geyim Bits Sorğu problemiBaxılıb 28

Problem bəyanat

Problem "Verilən aralığında dəyərləri olan sıra elementlərinin sayıları üçün sorğular" a tam array və iki ədəd x və y. Problem ifadəsi, verilən x və y arasında olan massivdə mövcud olan sayların sayını tapmağı xahiş edir.

misal

arr[]={2,4,6,8,1,10}
x = 2, y = 8
4

Izahat

Bir sıra içərisində 4, yəni 2, 4, 6 və 8 olmaqla 2 ilə 8 arasında olan XNUMX element var.

Verilən aralığında dəyərləri olan sıra elementlərinin sayı üçün sorğularPin

arr[]={2,4,6,8,1,10}
x = 5, y = 10
3

Izahat

Bir sıra içərisində 3, 6 və 8 olan 10 ilə 5-dən 10-a qədər olan elementlər olduğu üçün.

Alqoritm

  1. Cür massiv.
  2. İkili axtarışdan istifadə edərək y elementinin massivinin daha böyük indeksini tapın, daha böyük indeksini qaytarın.
  3. Ikili axtarışdan istifadə edərək x elementinin massivinin daha kiçik indeksini tapın, daha kiçik indeksini qaytarın.
  4. Daha böyük göstərici ilə kiçik indeks arasındakı fərqi və 1-i əlavə edin.

Izahat

Bir tam sıra və iki ədəd x və y ədəd verdik. Verilən x və y arasında yerləşən müəyyən bir massivdə mövcud olan ümumi rəqəmləri tapmağı xahiş etdik. Əsasən “x” -dan çox say sayını tapmaq məcburiyyətindəyik. Və “y” -dən kiçik rəqəmlərin sayı. Dizini sıralayacağıq. Bunun səbəbi ikili axtarış metodundan istifadə edəcəyimizdir. Bu da dəyişdirilir.

Nömrənin indeksini alın y ikili axtarışdan istifadə edərək massivdə. İkili axtarışda, y-nin olduğu indeksi tapmağa çalışırıq. Aşağı dəyər, yüksək dəyərdən az və ya bərabər olana qədər döngəni davam etdiririk. Adətən aşağı 0-cı indeks, yüksək isə serialın son indeksidir, çünki sıra indeksləri üzərində ikili axtarış aparırıq. İkili axtarışdan istifadə etməklə, hər bir sorğu üçün loqaritmik zaman mürəkkəbliyində verilmiş aralığında dəyərləri olan sıra elementlərinin sayı sorğularına cavab verməyə imkan verir.

Aşağı və yüksək dəyərin ortasını alacağıq və [orta] massivindəki elementin x-a bərabər olduğunu yoxlayacağıq. Bu doğrudursa, yüksək dəyərini 1-in ortasına qədər yeniləyin. Başqa bir səviyyəni aşağıdan + 1-ə qədər yeniləyin. Eyni element y ilə tətbiq olunmalıdır. Ancaq bu vəziyyətdə daha böyük indeks tapacağıq və serialın yoxlanılması əvəzinə [orta] y-yə bərabərdir. Ardından [orta] massivinin y-dən az olub-olmadığını yoxlamağa davam edin və aşağıdan orta + 1-ə qədər olanı və yüksəkdən 1-ə qədər olanları yeniləyin.

İndekslərin hər ikisini daha böyük və kiçik olaraq alın və fərqini qaytarın və üzərinə 1 əlavə edin. Bu, qaytarılmış tələb olunan cavabımız olacaq. Unutmayın, verilmiş aralığında dəyərləri olan sıra elementlərinin sayı üçün sorğuları cavablandırmaq istədik.

Kodu

Müəyyən bir aralıqdakı sıra elementlərinin sayını tapmaq üçün C ++ kodu

#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

Verilən aralıqdakı sıra elementlərinin sayını tapmaq üçün Java proqramı

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

Hər sorğu üçün vaxt olacaq O (log n) və serialı bir dəfə çeşidləmək üçün olacaq O (n log n).

Kosmik Mürəkkəblik

O (n) hara "N" massivdəki elementlərin sayıdır. Nəzərə aldığımız boşluq, serialın çeşidlənməsi zamanı alınan yer sayəsindədir. "Verilən aralığında dəyərləri olan sıra elementlərinin sayı üçün sorğular" problemində girişin saxlanması üçün lazım olan yer nəzərə alınmır.

Translate »