Шугаман хугацааны 3-р хэмжээтэй эрэмбэлэгдсэн дарааллыг ол


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Авалара Капитал Нэг Citadel Citrix Ebay Fab Синопсис
Array

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

"Шугаман хугацааны 3-р хэмжээтэй эрэмбэлсэн дэд дарааллыг олох" гэсэн асуудал танд байна бүхэл тоо массив. Асуудлын шийдэл нь гурван тоог массив [i] <массив [k] <массив [k], i <j <k гэсэн дарааллаар олж мэдэхийг хүсдэг.

Жишээ нь

arr[] = {11,34,2,5,1,7,4 }
2 5 7

Тайлбар

2 нь 5-аас бага, 5 нь 7-оос бага бөгөөд тэдгээрийн индексүүд бие биенээсээ бага байх ёстой.

Алгоритм

1. Declare a new array “small” and “great” of size as same as the original array.
2. Set the value of maximum to n-1, and the value of minimum to 0.
3. Marked the first element of the array we created to -1.
4. Traverse the array from i=1 to less than n(n is the length of the array).
  1. Check if arr[i] is smaller or equal to arr[minimum], if true
    1. Set minimum to i and small[i] to -1.
  2. Else put small[i] = minimum.
5. Traverse the array from i=n-2 to less than equal to 0(n is the length of the array).
  1. Check if arr[i] is greater than or equal to arr[maximum], if true
    1. Set maximum to i and great[i] to -1.
  2. Else put great[i] = maximum.
6. Traverse the array from i=0 to n and check if small[i] and great[i] is not equal to -1, then print the arr[small[i]] , arr[i] and arr[great[i]].
  1. Return

Тайлбар

Бидэнд байгаа массив of бүхэл тоо. Бид үүнийг олж мэдэхийг хүссэн эрэмбэлсэн өгөгдсөн массив дахь дараалал. Эрэмбэлсэн дараалал нь гурван тоог агуулсан бөгөөд тэдгээрийг бид эрэмбэлсэн дарааллаар олох ёстой бөгөөд энэ нь дарааллаар биш, хоорондоо уялдаатай боловч дарааллаар байх ёстой бөгөөд эхний дугаар нь хоёр дахь тооноос бага, хоёр дахь дугаар нь гурав дахь тооноос бага байх ёстой. хоёр дахь, гурав дахь нь дарааллаар ирэх ёстой.

Бид массивыг 1-ээс n-ээс бага замаар туулах бөгөөд эхний ба сүүлийн индекс элементийг хэвээр нь үлдээнэ. Бид эдгээр хоёрыг жижиг, гайхалтай массивт тэмдэглэсэн тул. Бид тэдгээрийн эхний ба индекс элементийг жижиг ба агуу массивын -1-тэй тэнцүү гэж тэмдэглэсэн. Массивыг дайран өнгөрч, arr [i] нь arr [minimum] -ээс бага эсвэл тэнцүү байгаа эсэхийг бид 1 гэж тэмдэглэсэн бол нөхцөл үнэн болохыг тогтоож, хамгийн бага утгыг i болгож шинэчилж одоогийн жижиг массивыг тэмдэглэ. элемент -0.

Үүнтэй ижил зүйлийг бид агуу массивтай хамт хийх болно, гэхдээ баруун талын хоёр дахь элементээс массивыг дамжуулж 0 хүртэл. Бид массивыг дайран өнгөрч arr [i] нь arr [хамгийн их буюу тэнцүү байх эсэхийг шалгана. ], хэрэв энэ нь үнэн бол бид хамгийн их утгыг 0, их [i] -ийг -1 болгож шинэчлэх хэрэгтэй. Бусад тохиолдолд бид дээд хэмжээг маш сайн байлгах болно [i]. Үүний дараа бид массивыг дахин туулж, жижиг [i] ба great [i] -1-тэй тэнцэхгүй байгаа эсэхийг шалгаж, хэрэв үнэн бол, дараа нь дурдсан утгуудыг хэвлэ.

Шугаман хугацааны 3-р хэмжээтэй эрэмбэлэгдсэн дарааллыг ол

 

код

C ++ кодыг шугаман хугацаанд 3 хэмжээтэй эрэмбэлсэн дарааллыг олох

#include<iostream>
using namespace std;

void getTriplet(int arr[], int n)
{
    int maximum = n - 1;
    int minimum = 0;
    int i;

    int* small = new int[n];

    small[0] = -1;
    for (i = 1; i < n; i++)
    {
        if (arr[i] <= arr[minimum])
        {
            minimum = i;
            small[i] = -1;
        }
        else
            small[i] = minimum;
    }

    int* great = new int[n];

    great[n - 1] = -1;
    for (i = n - 2; i >= 0; i--)
    {
        if (arr[i] >= arr[maximum])
        {
            maximum = i;
            great[i] = -1;
        }
        else
            great[i] = maximum;
    }

    for (i = 0; i < n; i++)
    {
        if (small[i] != -1 && great[i] != -1)
        {
            cout << arr[small[i]] << " " << arr[i] << " "<< arr[great[i]];
            return;
        }
    }

    cout << "3 numbers not found";

    delete[] small;
    delete[] great;

    return;
}
int main()
{
    int arr[] = { 11,34,2,5,1,7,4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    getTriplet(arr, n);
    return 0;
}
2 5 7

Шугаман хугацаанд 3 хэмжээтэй эрэмбэлэгдсэн дэд дарааллыг олох Java код

class SortedSubsequenceSize3
{
    public static void getTriplet(int arr[])
    {
        int n = arr.length;
        int maximum = n - 1;

        int minimum = 0;
        int i;

        int[] small = new int[n];

        small[0] = -1;
        for (i = 1; i < n; i++)
        {
            if (arr[i] <= arr[minimum])
            {
                minimum = i;
                small[i] = -1;
            }
            else
                small[i] = minimum;
        }
        int[] great = new int[n];

        great[n - 1] = -1;
        for (i = n - 2; i >= 0; i--)
        {
            if (arr[i] >= arr[maximum])
            {
                maximum = i;
                great[i] = -1;
            }
            else
                great[i] = maximum;
        }
        for (i = 0; i < n; i++)
        {
            if (small[i] != -1 && great[i] != -1)
            {
                System.out.println(arr[small[i]] + " " + arr[i] + " " + arr[great[i]]);
                return;
            }
        }
        System.out.println("3 numbers not found");
        return;
    }
    public static void main(String[] args)
    {
        int arr[] = { 11,34,2,5,1,7,4 };
        getTriplet(arr);
    }
}
2 5 7

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

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

O (N) хаана "N" нь массив дахь элементүүдийн тоо юм. Бид массивын бүх элементүүдийг туулсан. Массивын хэмжээ нь N тул цаг хугацааны нарийн төвөгтэй байдал нь мөн шугаман байдаг.

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

O (N) хаана "N" нь массив дахь элементүүдийн тоо юм. Бид массивын элемент бүрийн хувьд жижиг, том элементийг хадгалсаар ирсэн. Тиймээс орон зайн нарийн төвөгтэй байдал нь мөн шугаман юм.