Alt dizinin dağ şəklində olub olmadığını tapın

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur Amazon BlackRock Cisco Citrix Məlumat dəsti Honeywell Tesla Yandex
Geyim Sorğu problemiBaxılıb 21

Problem bəyanat

“Alt dizinin dağ şəklində olub olmadığını tapın” problemi sizə verildiyini bildirir tam array və bir sıra. Problem ifadəsi, verilən sıra arasında yaradılan alt dizinin dağ forması şəklində olub olmadığını öyrənməyi xahiş edir? Sayılar artan sırada və ya azalan sırada və ya əvvəlcə artdıqdan sonra azaldıqda dağ massivi yaranır.

misal

arr[]={3,4,5,6,1,5,1,2,1}

Left, right = (0, 3)
Mountain Form

Izahat

Çünki {3, 4, 5, 6} alt sıra artmaqdadır, buna görə dağ massivi şəklindədir.

Alt dizinin dağ şəklində olub olmadığını tapınPin

arr[]={3,4,5,6,1,5,1,2,1}

Left, right = (5, 7)
Not a Mountain form

Izahat

Çünki {5, 1, 2} alt massivi azaldıqdan sonra artır. Yəni dağ massivi şəklində deyil.

Alqoritm

  1. İki sıra yaradın massivmassivR orijinal massivin uzunluğu ilə eyni ölçüdədir.
  2. ArrayL-in ilk elementini və arrayR-in son elementini işə salın.
  3. Cari massiv elementi əvvəlki elementdən böyükdürsə.
    1. Yeniləyin artan say indeksə.
    2. ArrayL üçün artan sayı dəyərini təyin edin.
  4. Dizini sağdan sola keçir və sayının əvvəlki elementdən (cari elementin sağındakı element) böyük olub olmadığını yoxlayın.
    1. Sonra yeniləmə azalan say indeksə
    2. ArrayR-i azalan Sayıya təyin edin.
  5. Verilən hər bir sorğu üçün arrayR [left] arrayL [right] return true-dan böyükdür, əks halda false return.

Izahat

Tam bir sıra və sola, sağa bir sıra verdik. Verilən aralıqla bu şəkildə yaradılan subarrayın dağ massivi olub olmadığını öyrənməyimizi xahiş etdik. Əgər bu şəkildə yaradılan subarray dağ massividirsə, onda true, əks halda false olaraq qayıdacağıq. İki sıra elan edəcəyik. Biri massivin sol tərəfi, digəri isə massivin sağ tərəfi üçündür. Sonra hər bir sorğu daimi məkanda bir həll verə bilməsi üçün bu massivləri quracağıq.

ArrayL və arrayR yaratdığımız massivin ilk və son elementini müvafiq olaraq işə salacağıq. Sonra serialın sol tərəfi üçün sıra keçirik və ya soldan sağa deyə bilərik. Cari massiv elementinin əvvəlki elementdən az olması vəziyyətini yoxlayacağıq. Doğru olduğu aşkar edilərsə, artan sayını ədədin indeksinə qədər yeniləyəcəyik. Və arrayL-nin 'cari elementini şərtdən asılı olmayaraq hər dəfə doğru və ya olmadığına görə artıran Nömrəyə təyin edin.

Növbəti addımda biz massivi sağdan sola, əsasən ikinci son elementdən massivin birinci elementinə keçirik və massivin cari elementinin növbəti elementdən böyük olub olmadığını yoxlayacağıq. Sağdan sola keçdiyimiz üçün əvvəlki elementlə yoxlama deyə bilərik. Şərt doğru və ya doğrudursa, azalan Sayı dəyəri cari indeksə dəyişdirilir. Şərtlərdən asılı olmayaraq massivi azalan sayına qədər yeniləyin. Doğru qayıdın, əgər arrayR [sol] arrayL [sağ] dan böyük və ya ona bərabərdirsə, əks halda false qayıdır.

Kodu

Alt bölmənin dağ şəklində olub olmadığını tapmaq üçün C ++ kodu

#include<iostream>

using namespace std;

void buildArrays(int arr[], int N, int arrayL[], int arrayR[])
{
    arrayL[0] = 0;
    int increasingNumber = 0;

    for (int i = 1; i < N; i++)
    {
        if (arr[i] > arr[i - 1])
            increasingNumber = i;
        arrayL[i] = increasingNumber;
    }
    arrayR[N - 1] = N - 1;
    int decreasingNumber = N - 1;

    for (int i = N - 2; i >= 0; i--)
    {
        if (arr[i] > arr[i + 1])
            decreasingNumber = i;
        arrayR[i] = decreasingNumber;
    }
}

bool solveQuery(int arr[], int arrayL[], int arrayR[], int Left, int Right)
{
    return (arrayR[Left] >= arrayL[Right]);
}

int main()
{
    int arr[] = {3,4,5,6,1,5,1,2,1};
    int N = sizeof(arr) / sizeof(int);

    int arrayL[N], arrayR[N];
    buildArrays(arr, N, arrayL, arrayR);

    int L = 0;
    int R = 3;
    if (solveQuery(arr, arrayL, arrayR, L, R))
        cout << "Mountain form\n";
    else
        cout << "Not a mountain form\n";

    L = 5;
    R = 7;
    if (solveQuery(arr, arrayL, arrayR, L, R))
        cout << "Mountain form\n";
    else
        cout << "Not a mountain form\n";

    return 0;
}
Mountain form
Not a mountain form

Bir alt dizinin dağ şəklində olub olmadığını tapmaq üçün Java kodu

class MountainArray
{
    static void buildArrays(int arr[], int N, int arrayL[], int arrayR[])
    {
        arrayL[0] = 0;
        int increasingNumber = 0;

        for (int i = 1; i < N; i++)
        {
            if (arr[i] > arr[i - 1])
                increasingNumber = i;
            arrayL[i] = increasingNumber;
        }
        arrayR[N - 1] = N - 1;
        int decreasingNumber = N - 1;

        for (int i = N - 2; i >= 0; i--)
        {
            if (arr[i] > arr[i + 1])
                decreasingNumber = i;
            arrayR[i] = decreasingNumber;
        }
    }
    
    static boolean solveQuery(int arr[], int arrayL[], int arrayR[], int Left, int Right)
    {
        return (arrayR[Left] >= arrayL[Right]);
    }

    public static void main(String[] args)
    {
        int arr[] = {3,4,5,6,1,5,1,2,1};
        int N = arr.length;
        int arrayL[] = new int[N];
        int arrayR[] = new int[N];
        buildArrays(arr, N, arrayL, arrayR);
        int L = 0;
        int R = 3;

        if (solveQuery(arr, arrayL, arrayR, L, R))
            System.out.println("Mountain form");
        else
            System.out.println("Not a mountain form");

        L = 5;
        R = 7;

        if (solveQuery(arr, arrayL, arrayR, L, R))
            System.out.println("Mountain form");
        else
            System.out.println("Not a mountain form");
    }
}
Mountain form
Not a mountain form

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N + Q), hər iki massivi qurmaq üçün O (N) vaxt tələb edirik. Diziler qurulduqdan sonra. Suallara O (1) -də cavab verə bilərik.

Kosmik Mürəkkəblik

O (n) hara "N" massivdəki elementlərin sayıdır.

Translate »