रेषीय वेळेत आकार 3 ची क्रमवारी लावलेले अनुक्रम शोधा


अडचण पातळी मध्यम
वारंवार विचारले अवलारा कॅपिटल वन किल्ला सिट्रिक्स हा कोड eBay फॅब सारांश
अरे

समस्या विधान

"रेषीय वेळेत आकार 3 ची क्रमवारी लावलेले अनुक्रम शोधा" या समस्येमध्ये असे म्हटले आहे की आपल्याकडे पूर्णांक अॅरे. समस्या स्टेटमेंटमध्ये अ‍ॅरे [i] <अ‍ॅरे [के] <अ‍ॅरे [के] आणि आय <जे <के अशा प्रकारे तीन नंबर शोधण्यास सांगितले जाते.

उदाहरण

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 च्या समान असल्याचे चिन्हांकित केले. अ‍ॅरेचा शोध घेणे आणि rर [i] अररपेक्षा कमी किंवा समान आहे की नाही हे तपासा [किमान] जेथे किमान 0 असल्याचे चिन्हांकित केले, जर कंडिशन सत्य आढळली तर कमीतकमी i ची व्हॅल्यू अपडेट करा आणि सध्याचे छोटे अ‍ॅरे चिन्हांकित करा. घटक ते -1.

आपण ग्रेट अ‍ॅरेसह समान करू, परंतु अ‍ॅरेच्या ट्रॅव्हर्सलपासून दुसर्‍या घटकापासून उजव्या बाजूला ० पर्यंत जा. आम्ही अ‍ॅरेला मागे टाकू आणि अरर [i] एरपेक्षा मोठे किंवा समान आहे का ते तपासू [जास्तीत जास्त ], ते खरे असल्यास आम्हाला जास्तीत जास्त 0 आणि मूल्य [i] ते -0 पर्यंत अद्यतनित करावे लागेल. अन्यथा आम्ही जास्तीत जास्त उत्कृष्ट ठेवू [i]. यानंतर आपण पुन्हा अ‍ॅरे मागे जाऊ आणि लहान [i] आणि महान [i] -1 बरोबर नसल्यास तपासू, जर ते खरे असेल तर नमूद केलेली व्हॅल्यूज प्रिंट करू.

रेषीय वेळेत आकार 3 ची क्रमवारी लावलेले अनुक्रम शोधा

 

कोड

रेषीय वेळेत आकार 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) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या. आम्ही अ‍ॅरेच्या सर्व घटकांचा मागोवा घेतला आहे. आणि अ‍ॅरेचा आकार एन आहे कारण वेळची जटिलता देखील रेषात्मक आहे.

स्पेस कॉम्प्लेक्सिटी

O (n) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या. आम्ही प्रत्येक अ‍ॅरे घटकासाठी छोटे आणि मोठे घटक संग्रहित करत आहोत. अशा प्रकारे अवकाशातील अवघडपणा देखील रेषात्मक आहे.