Տրված տիրույթի արժեքներով զանգվածի տարրերի հաշվարկի հարցումներ  


Դժվարության մակարդակ Դժվար
Հաճախակի հարցնում են Coursera ԴԵ Շոուն Google PayU Snapdeal Times ինտերնետ Անտաշ անասուն նողկալի արարած
Դասավորություն Բիթեր Հարցման խնդիր

Խնդիրի հայտարարություն  

«Տրված տիրույթում արժեքների զանգվածի տարրերի հաշվարկի հարցումներ» խնդիրը ասում է, որ դուք ունեք ամբողջ թիվ դասավորություն և երկու թիվ x և y: Խնդրի հայտարարությունը խնդրում է պարզել զանգվածում առկա թվերի քանակը, որը ընկած է տրված x- ի և y- ի միջև:

Օրինակ  

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

բացատրություն

Քանի որ զանգվածում առկա է 4 տարր, այսինքն ՝ 2, 4, 6 և 8, որոնք ընկած են 2-ի և 8-ի միջև, ներառյալ:

Տրված տիրույթի արժեքներով զանգվածի տարրերի հաշվարկի հարցումներPin

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-րդ ինդեքսն է, իսկ բարձրը ՝ զանգվածի վերջին ինդեքսը, քանի որ մենք երկուական որոնում ենք կատարում զանգվածի ինդեքսների վրա: Երկուական որոնման օգտագործումը մեզ թույլ է տալիս պատասխանել յուրաքանչյուր հարցման համար լոգարիթմական ժամանակի բարդության մեջ զանգվածի տարրերի քանակի քանակի տարրերի հաշվարկի հարցումներին:

Մենք կստանանք ցածր և բարձր արժեքի կեսը և ստուգենք ՝ արդյոք [mid] զանգվածում առկա տարրը x- ից հավասար է: Եթե ​​դա ճիշտ է, ապա բարձրացրու բարձր արժեքը 1-ի կեսին: Այլապես թարմացրեք ցածրից մինչև կես + արժեքը: Նույնը կիրառվում է y տարրի հետ: Բայց այդ դեպքում մենք կգտնենք ավելի մեծ ցուցանիշ, և զանգվածը ստուգելու փոխարեն y- ն հավասար է: Դրանից հետո շարունակեք ստուգել, ​​թե արդյոք զանգվածը [կեսը] պակաս է 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

Տվյալ տիրույթում զանգվածի տարրերի հաշվարկը գտնելու 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

Բարդության վերլուծություն  

Timeամանակի բարդություն

Յուրաքանչյուր հարցման գործարկման ժամանակը կլինի O (տեղեկամատյան n) և զանգվածը մեկ անգամ տեսակավորելու համար կլինի O (n տեղեկամատյան n).

Տես նաեւ,
Ինչպե՞ս ստուգել, ​​արդյոք տրված երկու հավաքածուները տարանջատված են:

Տիեզերական բարդություն

O (n) որտեղ «Ն» զանգվածում տարրերի քանակն է: Մեր դիտարկած տարածքը զանգվածի տեսակավորման ընթացքում վերցված տարածության պատճառով է: Ներածումը պահելու համար պահանջվող տարածքը չի դիտարկվում «Տրված տիրույթում արժեքներ ունեցող զանգվածի տարրերի հաշվարկի հարցում» խնդրում: