نمایشگرهای شمارش عناصر آرایه با مقادیر در دامنه داده شده


سطح دشواری سخت
اغلب در Coursera دی شاو گوگل PayU اسنپدل بار اینترنت یاهو
صف بیت مشکل پرس و جو

بیان مسأله

مسئله "پرس و جو برای شمارش عناصر آرایه با مقادیر در دامنه داده شده" بیان می کند که شما دارای یک عدد صحیح صف و دو عدد 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 در آن وجود دارد. حلقه را ادامه می دهیم تا زمانی که مقدار 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

برنامه جاوا برای یافتن تعداد عناصر آرایه در یک محدوده داده شده

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

تحلیل پیچیدگی

پیچیدگی زمان

زمان اجرای هر سeryال خواهد بود O (ورود به سیستم) و برای مرتب سازی آرایه یک بار خواهد بود O (n log n).

پیچیدگی فضا

O (N) جایی که "n" تعداد عناصر آرایه است. فضایی که در نظر گرفتیم به دلیل فضای گرفته شده در هنگام مرتب سازی آرایه است. فضای مورد نیاز برای ذخیره ورودی در مسئله "پرس و جو برای شمارش عناصر آرایه با مقادیر در دامنه داده شده" در نظر گرفته نشده است.