Брой индекси с равни елементи в даден диапазон


Ниво на трудност M
Често задавани в GreyOrange Наистина опера Pinterest Snapdeal Yahoo
Array Задача за заявка

Вие получавате цяло число масив, q заявки и диапазон отляво и отдясно. „Броят на индексите с равни елементи в даден диапазон“ казва да се намери общият брой на целите числа по такъв начин, че ляво <= i <дясно, така че Ai = Аj + 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.