लाइनर टाइममा आकार of को क्रमबद्ध अनुभाग फेला पार्नुहोस्


कठिनाई तह मध्यम
बारम्बार सोधिन्छ Avalara राजधानी एक Citadel citrix eBay फेब Synopsys
एरे

समस्या वक्तव्य

समस्या "लाइनर टाइममा आकार qu को क्रमबद्ध अनुक्रमणिका फेला पार्नुहोस्" भन्छ कि तपाईसँग पूर्णांक array। समस्या कथनले तीन अ numbers्क पत्ता लगाउन को लागी यस्तो तरिकामा सोध्छ कि एर्रे [i] <एर्रे [k] <एर्रे [k], र i <j <k।

उदाहरणका

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

स्पष्टीकरण

२ 2 भन्दा कम छ र 5 भन्दा कम छ, र तिनीहरूको सूचकांकहरू एक अर्का भन्दा कम छन्।

अल्गोरिदम

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

स्पष्टीकरण

हामीसँग छ array of पूर्णांक। हामीले यो पत्ता लगाउन सोध्यौं क्रमबद्ध दिइएको एर्रेमा subquence। क्रमबद्ध अनुक्रममा तीन नम्बरहरू समावेश छन् जुन हामीले क्रमबद्ध क्रममा फेला पार्नुपर्दछ र यो अनुक्रममा हुनुपर्दछ, जोडदार ढंगले होइन तर अनुक्रममा, पहिलो नम्बर दोस्रो नम्बर भन्दा कम हुनुपर्दछ र दोस्रो नम्बर तेस्रो नम्बर भन्दा कम हुनुपर्दछ, र पहिले, दोस्रो र तेस्रो क्रममा आउनु पर्छ।

हामी एरेलाई १ बाट n भन्दा कममा जाँदैछौं, हामी पहिलो र अन्तिम अनुक्रमणिका एलिमेन्ट छोड्नेछौं। किनकी हामीले ती -1 लाई दुई एरेमा सिर्जना गरेका थियौं, सानो र ठूलो। हामीले उनीहरूको पहिलो र अनुक्रमणिका तत्व क्रमश: सानो र ठूलो एरेको -1 को बराबर हो भनेर चिन्ह लगायौं। एर्रे ट्र्याभिंग र जाँच गर्नुहोस् यदि एर [i] arr भन्दा कम वा बराबर हो [न्यूनतम] जहाँ न्यूनतम हामीले ० को रूपमा चिन्ह लगायौं, यदि कन्डिसन सत्य छ भने, तब i को कम से कम मान अपडेट गर्नुहोस्, र हालको सानो सानो एरेमा चिन्ह लगाउनुहोस्। एलिमेन्ट -१।

समान चीज हामी महान एर्रेसँग गर्छौं, तर एर्रेको ट्राभर्सलबाट दायाँ तर्फको दोस्रो एलिमेन्टबाट ० सम्म। हामी एर्रे पार गर्नेछौं र जाँच्नेछौं यदि एर [i] ठूलो वा ठूलो हो बराबर हो [अधिकतम ], यदि यो सत्य हो भने हामीले अधिकतम ० र महान [i] लाई -१ मा मूल्य अपडेट गर्नुपर्नेछ। अन्यथा हामी अधिकतम उत्कृष्ट [i] राख्नेछौं। यस पछि हामी फेरि एर्रे ट्र्यावर्संग गर्छौं र सानो [i] र ठूलो [i] -0 को बराबर छैन भने जाँच गर्छौं, यदि यो सहि छ भने, तब उल्लेखित मानहरू प्रिन्ट गर्नुहोस्

लाइनर टाइममा आकार of को क्रमबद्ध अनुभाग फेला पार्नुहोस्

 

कोड

सी ++ कोड लाइनर समय मा आकार size को क्रमबद्ध अनुभाग खोज्न

#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

जाभा कोड लाइनर समय मा आकार size को क्रमबद्ध अनुगामी खोज्न

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" एर्रेमा एलिमेन्ट्सको संख्या हो। हामी प्रत्येक एर्रे एलिमेन्टको लागि सानो र ठूलो एलिमेन्ट भण्डार गर्दै छौं। यसैले स्पेस जटिलता पनि रैखिक छ।