მოცემულ დიაპაზონში თანაბარი ელემენტების მქონე ინდექსების რაოდენობა


Რთული ტური საშუალო
ხშირად ეკითხებიან რუხი ნარინჯისფერი ნამდვილად ოპერისა Pinterest Snapdeal Yahoo
Array შეკითხვის პრობლემა

თქვენ გეძლევათ მთელი რიცხვი მასივი, q მოთხოვნები და დიაპაზონი მარცხნივ და მარჯვნივ. ”მოცემულ დიაპაზონში თანაბარი ელემენტების მქონე ინდექსების რაოდენობა” ამბობს მთელი რიცხვების მთლიანი რაოდენობის გასარკვევად ისე, რომ დატოვა <= i <მარჯვნივ, ისე რომ Ai = აკ +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

ჯავის კოდი დათვლის დიაპაზონში თანაბარი ელემენტების მქონე ინდექსების რაოდენობა

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) ყველა მოთხოვნისთვის და O (n) წინასწარი გამოთვლისთვის.

სივრცის სირთულე

O (n) სადაც "ნ" არის მასივის ელემენტების რაოდენობა. ეს სივრცე საჭიროა arrayDummy- ს შესაქმნელად.