Колькасць індэксаў з аднолькавымі элементамі ў дадзеным дыяпазоне


Узровень складанасці серада
Часта пытаюцца ў Шэры Аранжавы Сапраўды Опера Pinterest Snapdeal Yahoo
масіў Задача запыту

Вам дадзена цэлае масіў, q запыты і дыяпазон злева і справа. «Колькасць індэксаў з аднолькавымі элементамі ў дадзеным дыяпазоне» кажа, каб высветліць агульную колькасць падлікаў цэлых лікаў такім чынам, каб злева <= i <направа, так, каб Ai = Aj + 1.

Прыклад

arr[] = {2, 2, 3, 3, 3, 4, 4, 4, 4}
Query = 2
Left = 2, right = 6
Left = 4, right = 8
3
3

Тлумачэнне

Для запыту1, дзе злева = 2, справа = 6

arr[2]=arr[3], arr[3]=arr[4], arr[5]=arr[6]

Колькасць - 3.

Для запыту2, дзе злева = 4, справа = 8

arr[5]=arr[6], arr[6]=arr[7], arr[7]=arr[8]

Колькасць - 3.

Колькасць індэксаў з аднолькавымі элементамі ў дадзеным дыяпазоне

 

Алгарытм

  1. Стварыце масіў.
  2. Прайсці па масіве.
  3. Калі бягучы элемент масіва роўны наступнаму элементу, адзначце элемент створанага масіва роўным 1.
  4. Калі індэкс не роўны 0, тады захоўвайце суму бягучага элемента масіва arrayDummy і наступнага элемента масіва ў arrayDummy [i].
  5. Вырашыце запыт, калі левая пазіцыя роўная 0, затым вярніце arrayDummy [справа-1], у адваротным выпадку вернеце розніцу arrayDummy [справа-1] і arrayDummy [злева-1].

Тлумачэнне

Нам дадзена цэлае масіў і дыяпазон як левы бок, так і правы бок. Нас просяць даведацца колькасць індэксаў такім чынам, каб суседнія элементы былі роўныя адзін аднаму. Калі мы знайшлі два роўныя суседнія элементы з двума рознымі індэксамі, тады палічыце 1 і гэтак далей. Затым ствараем масіў максімальнага памеру. Мы стварылі функцыю, якая падлічвае індэкс, які задавальняе дадзенай умове. Умова заключаецца ў тым, што два суседнія элементы роўныя адзін аднаму.

Мы пройдзем па масіве ад пачатку да таго, які менш даўжыні масіва. Тады мы правяраем, ці роўны бягучы элемент масіва наступнаму элементу масіва. Калі ўмова будзе прызнана праўдзівай. Затым мы адзначаем гэта значэнне ў бягучым індэксе 'да 1. Мы будзем пазначаць гэта 1, таму што даведаемся, ці роўны любы з суседніх элементаў. Тады кожная пара лічыцца лікам 1, наступная пара з адным элементам, агульным для папярэдняй пары, будзе лічыцца 2 і г.д. Калі n пар роўна, будзе лічыцца n-1. Таксама калі значэнне індэкса не роўна 0. Гэта азначае, што падчас перамяшчэння гэта не першы элемент. Захоўваеце суму бягучага элемента arrayDummy і папярэдняга элемента ў бягучым індэксе arrayDummy.

Для кожнага зададзенага запыту, калі левы індэкс дыяпазону роўны 0, вяртаецца arrayDummy [справа - 1]. У адваротным выпадку, калі гэта не 0, проста вярніце розніцу паміж arrayDummy [справа - 1] і arrayDummy [злева - 1].

код

Код C ++ для падліку Колькасць індэксаў з аднолькавымі элементамі ў зададзеным дыяпазоне

#include <iostream>

using namespace std;

int arrayDummy[100];

void getNumbers(int a[], int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        if (a[i] == a[i + que
            arrayDummy[i] = 1;

        if (i != 0)
            arrayDummy[i] += arrayDummy[i - 1];
    }
}

int solveQuery(int l, int r)
{
    if (l == 0)
        return arrayDummy[r - 1];
    else
        return arrayDummy[r - 1] - arrayDummy[l - 1];
}

int main()
{
    int arr[] = { 2,2,3,3,3,4,4,4,4};
    int n = sizeof(arr) / sizeof(arr[0]);

    getNumbers(arr, n);

    int left, right;

    left = 2;
    right = 6;

    cout << solveQuery(left, right) << endl;
    left = 4;
    right = 8;
    cout << solveQuery(left, right) << endl;
    return 0;
}
3
3

Код Java для падліку Колькасць індэксаў з аднолькавымі элементамі ў зададзеным дыяпазоне

class IndexElementsEqual
{
    static int arrayDummy[] = new int[1000];

    public static void getNumbers(int arr[], int n)
    {
        for (int i = 0; i < n-1; i++)
        {
            if (arr[i] == arr[i + 1])
                arrayDummy[i] = 1;

            if (i != 0)
                arrayDummy[i] += arrayDummy[i - 1];
        }
    }
    public static int solveQuery(int left, int right)
    {
        if (left == 0)
            return arrayDummy[right - 1];
        else
            return arrayDummy[right - 1] - arrayDummy[left - 1];
    }
    public static void main(String args[])
    {
        int arr[] = {2,2,3,3,3,4,4,4,4};
        int n = arr.length;

        getNumbers(arr, n);

        int left, right;

        left = 2;
        right = 6;

        System.out.println(solveQuery(left, right));
        left = 4;
        right = 8;
        System.out.println(solveQuery(left, right));
    }
}
3
3

Аналіз складанасці

Складанасць часу

 O (1) для кожнага запыту і Аб (п) для папярэдніх вылічэнняў.

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

Аб (п) дзе "П" - колькасць элементаў у масіве. Гэта прастора неабходна для стварэння arrayDummy.