دنباله مرتب شده از اندازه 3 را در زمان خطی پیدا کنید


سطح دشواری متوسط
اغلب در Avalara یکی از سرمایه دژ خودتان هستید؟ ای بی فاب Synopsys
صف

بیان مسأله

مسئله "یک دنباله مرتب شده از اندازه 3 در زمان خطی پیدا کنید" بیان می کند که شما یک دارید عدد صحیح صف. بیانیه مسئله می خواهد سه عدد را به گونه ای پیدا کند که آرایه [i] <array [k] <array [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 را در دو آرایه ایجاد شده ، کوچک و بزرگ علامت گذاری کرده ایم. ما اولین عنصر و شاخص آنها را به ترتیب برابر با 1 آرایه های کوچک و بزرگ نشان دادیم. عبور از آرایه و بررسی اینکه آیا ar [i] کمتر یا مساوی arr است [حداقل] که حداقل ما آن را 0 نشان دادیم ، اگر شرط درست تشخیص داده شود ، سپس مقدار حداقل را به i به روز کنید و آرایه کوچک فعلی را علامت گذاری کنید عنصر به -1.

همان کاری که با آرایه بزرگ انجام خواهیم داد ، اما با عبور از آرایه از عنصر دوم سمت راست به 0. ما آرایه را رد می کنیم و بررسی می کنیم که آیا ar [i] بزرگتر یا برابر arr است [حداکثر ] ، اگر درست باشد ، ما باید مقدار حداکثر را به 0 و بزرگ [i] را به -1 به روز کنیم. در غیر این صورت ما حداکثر را به عنوان بزرگ قرار خواهیم داد [i]. بعد از این ، ما دوباره آرایه را رد می کنیم و بررسی می کنیم که آیا کوچک [i] و بزرگ [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 در زمان خطی

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" تعداد عناصر آرایه است. ما عنصر کوچکتر و بزرگتر را برای هر عنصر آرایه ذخیره کرده ایم. بنابراین پیچیدگی فضا نیز خطی است.