געפֿינען אַ סאָרטעד סאַבסאַקוואַנס פון גרייס 3 אין לינעאַר צייט


שוועריקייט לעוועל מיטל
אָפט געבעטן אין אַוואַלאַראַ Capital One ציטאַדעל סיטריקס עבייַ Fab סינאָפּסיס
מענגע

פּראָבלעם סטאַטעמענט

די פּראָבלעם "געפֿינען אַ סאָרטעד סאַבסאַקוואַנס פון גרייס 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 ינטעגער. מיר האָבן געבעטן צו געפינען אויס די sorted דערנאָך אין די געגעבן מענגע. די סאָרטעד סאַבסאַקוואַנס כּולל דרייַ נומערן וואָס מיר האָבן צו געפֿינען אין סדר סדר און עס זאָל זיין אין סיקוואַנס, נישט קאַנטיגיואַסלי, אָבער אין סיקוואַנס, דער ערשטער נומער זאָל זיין ווייניקער ווי די רגע נומער און די רגע נומער זאָל זיין ווייניקער ווי די דריט נומער און ערשטער, רגע און דריט זאָל קומען אין סדר.

מיר וועלן דורכגיין די מענגע פון ​​1 צו ווייניקער ווי N, און דער ערשטער און לעצט אינדעקס עלעמענט וועט לאָזן ווי עס איז. ווייַל מיר האָבן אנגעצייכנט די -1 אין די צוויי ערייזאַז מיר באשאפן, קליין און גרויס. מיר האָבן אנגעצייכנט זייער ערשטער און אינדעקס עלעמענט איז גלייַך צו -1 פון ריספּעקטיוולי קליין און גרויס ערייז. דורכפאָר די מענגע און קאָנטראָלירן אויב אַרר [איך] איז ווייניקער ווי אָדער גלייַך צו אַרר [מינימום] ווו מינימום מיר אנגעצייכנט ווי 0, אויב די צושטאַנד איז געפֿונען צו זיין אמת, דערהייַנטיקן די ווערט פון מינימום צו איך און אָפּגעמערקט קראַנט קליין מענגע. עלעמענט צו -1.

די זעלבע זאַך מיר וועלן טאָן מיט די גרויס מענגע, אָבער מיט די דורכפאָר פון די מענגע פֿון די רגע עלעמענט פון די רעכט זייַט צו 0. מיר וועלן אַריבער די מענגע און טשעק אויב אַרר [i] איז גרעסער ווי אָדער גלייַך צו אַרר [מאַקסימום ], אויב עס איז אמת, מיר האָבן צו דערהייַנטיקן די ווערט פון מאַקסימום צו 0 און גרויס [איך] צו -1. אַנדערש מיר וועלן שטעלן די מאַקסימום ווי גרויס [איך]. נאָך דעם, מיר וועלן אַריבער די מענגע ווידער און טשעק אויב קליין [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

Java Code צו געפֿינען אַ סאָרטירט סאַבסטאַנסאַז פון גרייס 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

קאַמפּלעקסיטי אַנאַליסיס

צייט קאַמפּלעקסיטי

אָ (N) ווו “N” איז די נומער פון עלעמענטן אין די מענגע. מיר האָבן דורכגעקאָכט אַלע די מענגע עלעמענטן. און ווייַל די גרייס פון דעם מענגע איז N. די צייט קאַמפּלעקסיטי איז אויך לינעאַר.

ספעיס קאַמפּלעקסיטי

אָ (N) ווו “N” איז די נומער פון עלעמענטן אין די מענגע. מיר האָבן שוין סטאָרד דער קלענערער און גרעסערע עלעמענט פֿאַר יעדער מענגע עלעמענט. אזוי די פּלאַץ קאַמפּלעקסיטי איז אויך לינעאַר.