Дэд массив нь уулын хэлбэртэй эсэхийг олж мэд


Хэцүү байдлын түвшин Хатуу
Байнга асуудаг Амазоны БлэкРок Cisco Citrix Factset Honeywell Tesla Yandex
Array Асуулгын асуудал

Асуудлын мэдэгдэл

“Дэд цуваа уулын хэлбэртэй эсэхийг олж мэд” гэсэн асуудалд танд бүхэл тоо массив ба хүрээ. Асуудлын шийдэл нь өгөгдсөн мужийн хооронд үүссэн дэд массив нь уулын хэлбэртэй эсэхийг олж мэдэхийг хүсч байна уу? Тоонууд өсөх дарааллаар эсвэл буурах дарааллаар эсвэл эхлээд өсөөд дараа нь буурч байвал уулын массив үүснэ.

Жишээ нь

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

Left, right = (0, 3)
Mountain Form

Тайлбар

Учир нь {3, 4, 5, 6} дэд массив нэмэгдэж байгаа тул уулын массив хэлбэртэй байна.

Дэд массив нь уулын хэлбэртэй эсэхийг олж мэд

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

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

Тайлбар

Учир нь {5, 1, 2} дэд массив багасч дараа нь нэмэгдэж байна. Тиймээс энэ нь уулын массив хэлбэр биш юм.

Алгоритм

  1. Хоёр массив үүсгэх массив L болон массив R анхны массивын урттай ижил хэмжээтэй байна.
  2. Массивын эхний элемент болон массивын сүүлчийн элементийг эхлүүлнэ.
  3. Хэрэв одоогийн массивын элемент өмнөх элементээс их бол.
    1. Шинэчлэх нэмэгдэж байгаа тоо индекс рүү.
    2. Массивт нэмэгдэж буй дугаарыг оноож өг.
  4. Массивыг баруун талаас зүүн тийш дайран өнгөрч, өмнөх элементээс (одоогийн элементийн баруун талд байрлах элемент) том хэмжээтэй эсэхийг шалгана уу.
    1. Дараа нь буурч байгаа тоо индекс рүү
    2. Массивыг багасгахын тулд тоог оноох.
  5. Өгөгдсөн асуулга бүрийн хувьд arrayR [зүүн] нь arrayL [баруун] буцаах үнэнээс том, өөрөөр буцаах нь худал юм.

Тайлбар

Бид бүхэл тоон массив ба зүүнээс баруун тийш муж өгсөн. Өгөгдсөн хүрээний дагуу үүссэн дэд хэсэг нь уулын массив байж болох уу, үгүй ​​юу гэдгийг олж мэдэхийг хүссэн. Хэрэв ийм үүссэн дэд массив нь уулын массив бол бид үнэн буцаах болно, өөрөөр хэлбэл худлаа буцаана. Бид хоёр массивыг зарлах болно. Нэг нь массивын зүүн талд, нөгөө нь массивын баруун талд зориулагдсан болно. Асуулт бүр тогтмол орон зайд шийдэл гаргахын тулд бид эдгээр массивуудыг барьж байгуулах болно.

Бид arrayL ба arrayR-ийг үүсгэсэн массивын эхний ба сүүлчийн элементийг тус тусад нь эхлүүлнэ. Дараа нь бид массивын зүүн талын массивыг дайран өнгөрөх эсвэл зүүнээс баруун тийш хэлж болно. Одоогийн массивын элемент өмнөх элементээс бага байвал бид нөхцөл байдлыг шалгана. Хэрэв энэ нь үнэн болох нь тогтоогдвол бид нэмэгдэж буй дугаарыг тухайн тооны индекс болгон шинэчлэх болно. ArrayL-ийн 'одоогийн элементийг нөхцлөөс үл хамааран үнэн эсэхээс үл хамааран нэмэгдэж буй тоо руу хуваарилна уу.

Дараагийн алхам дээр бид массивыг баруунаас зүүн тийш, үндсэндээ сүүлчийн хоёр дахь элементээс массивын эхний элемент хүртэл дайрч, массивын одоогийн элемент дараагийн элементээс их байгаа эсэхийг шалгах болно. Бид баруунаас зүүн тийш явж байгаа тул өмнөх элементтэй хамт чек гэж хэлж болно. Хэрэв нөхцөл нь зөв эсвэл үнэн бол буурч байгаа тоон утгыг одоогийн индекс болгон өөрчилнө. Нөхцөлөөс үл хамааран массивыг тоо буурч тоогоор шинэчлэх. Буцаад үнэн, хэрэв массивR [зүүн] массиваас их эсвэл тэнцүү бол [баруун], өөрөөр буцаана.

код

Дэд массив нь уулын хэлбэртэй эсэхийг харуулах C ++ код

#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

Дэд массив нь уулын хэлбэртэй эсэхийг олж мэдэх Java код

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

Нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

O (N + Q), массивыг хоёуланг нь байгуулахад O (N) хугацаа шаардагдана. Массивыг барьсны дараа. Бид O (1) хэсэгт байгаа асуултанд хариулж болно.

Сансрын нарийн төвөгтэй байдал

O (N) хаана "N" массив дахь элементүүдийн тоо юм.