ਲੀਨੀਅਰ ਟਾਈਮ ਵਿੱਚ ਸਾਈਜ਼ 3 ਦਾ ਇੱਕ ਕ੍ਰਮਬੱਧ ਅਨੁਪਾਤ ਲੱਭੋ


ਮੁਸ਼ਕਲ ਪੱਧਰ ਦਰਮਿਆਨੇ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਅਵਲਾਰਾ ਕੈਪੀਟਲ ਇਕ ਕਿਲੇ ਸਿਟ੍ਰਿਕਸ ਈਬੇ ਫੈਬ ਸਿਨੋਪੋਸਿਸ
ਅਰੇ

ਸਮੱਸਿਆ ਦਾ ਬਿਆਨ

ਸਮੱਸਿਆ "ਲਾਈਨ ਟਾਈਮ ਵਿੱਚ ਅਕਾਰ 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 ਤੋਂ ਘੱਟ ਕਰਨ ਜਾ ਰਹੇ ਹਾਂ, ਅਸੀਂ ਪਹਿਲੇ ਅਤੇ ਆਖਰੀ ਇੰਡੈਕਸ ਐਲੀਮੈਂਟ ਨੂੰ ਜਿਵੇਂ ਛੱਡ ਦੇਵਾਂਗੇ. ਕਿਉਂਕਿ ਅਸੀਂ ਉਨ੍ਹਾਂ ਨੂੰ ਉਹਨਾਂ ਦੋ ਐਰੇ ਵਿਚ ਨਿਸ਼ਾਨਬੱਧ ਕੀਤਾ ਹੈ ਜੋ ਅਸੀਂ ਛੋਟੇ ਅਤੇ ਵੱਡੇ ਬਣਾਏ ਹਨ. ਅਸੀਂ ਉਨ੍ਹਾਂ ਦਾ ਪਹਿਲਾ ਅਤੇ ਸੂਚਕਾਂਕ ਤੱਤ ਕ੍ਰਮਵਾਰ ਛੋਟੇ ਅਤੇ ਮਹਾਨ ਐਰੇ ਦੇ ਬਰਾਬਰ ਹੈ. ਐਰੇ ਦਾ ਪਤਾ ਲਗਾਉਣਾ ਅਤੇ ਜਾਂਚ ਕਰੋ ਕਿ ਕੀ ਐਰ [i] ਆਰਰ ਤੋਂ ਘੱਟ ਜਾਂ ਇਸਦੇ ਬਰਾਬਰ ਹੈ [ਘੱਟੋ ਘੱਟ] ਜਿੱਥੇ ਘੱਟੋ ਘੱਟ ਸਾਨੂੰ 1 ਦੇ ਤੌਰ ਤੇ ਨਿਸ਼ਾਨਬੱਧ ਕੀਤਾ ਗਿਆ ਹੈ, ਜੇ ਸਥਿਤੀ ਸਹੀ ਪਾਈ ਜਾਂਦੀ ਹੈ, ਤਾਂ ਘੱਟੋ ਘੱਟ i ਦਾ ਮੁੱਲ ਅਪਡੇਟ ਕਰੋ, ਅਤੇ ਮੌਜੂਦਾ ਛੋਟੀ ਐਰੇ ਨੂੰ ਮਾਰਕ ਕਰੋ. ਤੱਤ ਨੂੰ -1.

ਉਹੀ ਚੀਜ਼ ਜੋ ਅਸੀਂ ਮਹਾਨ ਐਰੇ ਨਾਲ ਕਰਾਂਗੇ, ਪਰ ਐਰੇ ਦੇ ਟ੍ਰਾਵਰਸਲ ਤੋਂ ਦੂਜੇ ਪਾਸੇ ਦੇ ਸੱਜੇ ਪਾਸੇ 0 ਤੱਕ. ਅਸੀਂ ਐਰੇ ਨੂੰ ਪਾਰ ਕਰਾਂਗੇ ਅਤੇ ਜਾਂਚ ਕਰਾਂਗੇ ਕਿ ਕੀ ਐਰ [i] ਏਰ ਤੋਂ ਵੱਡਾ ਹੈ ਜਾਂ ਬਰਾਬਰ ਹੈ [ਅਧਿਕਤਮ ], ਜੇ ਇਹ ਸੱਚ ਹੈ ਤਾਂ ਸਾਨੂੰ ਵੱਧ ਤੋਂ ਵੱਧ 0 ਅਤੇ ਮਹਾਨ [i] ਤੋਂ -1 ਦੇ ਮੁੱਲ ਨੂੰ ਅਪਡੇਟ ਕਰਨਾ ਹੋਵੇਗਾ. ਨਹੀਂ ਤਾਂ ਅਸੀਂ ਵੱਧ ਤੋਂ ਵੱਧ ਮਹਾਨ ਪਾਵਾਂਗੇ [i]. ਇਸਦੇ ਬਾਅਦ, ਅਸੀਂ ਫਿਰ ਐਰੇ ਨੂੰ ਪਾਰ ਕਰਾਂਗੇ ਅਤੇ ਜਾਂਚ ਕਰਾਂਗੇ ਕਿ ਕੀ ਛੋਟਾ [i] ਅਤੇ ਮਹਾਨ [i] -1 ਦੇ ਬਰਾਬਰ ਨਹੀਂ ਹੈ, ਜੇ ਇਹ ਸਹੀ ਹੈ, ਤਾਂ ਦੱਸੇ ਗਏ ਮੁੱਲ ਪ੍ਰਿੰਟ ਕਰੋ.

ਲੀਨੀਅਰ ਟਾਈਮ ਵਿੱਚ ਸਾਈਜ਼ 3 ਦਾ ਇੱਕ ਕ੍ਰਮਬੱਧ ਅਨੁਪਾਤ ਲੱਭੋ

 

ਕੋਡ

ਲਕੀਰ ਸਮੇਂ ਵਿੱਚ ਆਕਾਰ 3 ਦੀ ਕ੍ਰਮਬੱਧ ਅਨੁਸਾਰੀ ਖੋਜ ਲਈ C ++ ਕੋਡ

#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

ਜਟਿਲਤਾ ਵਿਸ਼ਲੇਸ਼ਣ

ਟਾਈਮ ਜਟਿਲਤਾ

ਹੇ (n) ਜਿੱਥੇ ਕਿ “ਐਨ” ਐਰੇ ਵਿਚਲੇ ਤੱਤਾਂ ਦੀ ਗਿਣਤੀ ਹੈ. ਅਸੀਂ ਸਾਰੇ ਐਰੇ ਤੱਤ ਪਾਰ ਕਰ ਲਏ ਹਨ. ਅਤੇ ਕਿਉਂਕਿ ਐਰੇ ਦਾ ਆਕਾਰ N ਹੈ. ਸਮੇਂ ਦੀ ਜਟਿਲਤਾ ਵੀ ਲਕੀਰ ਹੁੰਦੀ ਹੈ.

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ

ਹੇ (n) ਜਿੱਥੇ ਕਿ “ਐਨ” ਐਰੇ ਵਿਚਲੇ ਤੱਤਾਂ ਦੀ ਗਿਣਤੀ ਹੈ. ਅਸੀਂ ਹਰੇਕ ਐਰੇ ਐਲੀਮੈਂਟਮੈਂਟ ਲਈ ਛੋਟੇ ਅਤੇ ਵੱਡੇ ਐਲੀਮੈਂਟ ਨੂੰ ਸਟੋਰ ਕਰ ਰਹੇ ਹਾਂ. ਇਸ ਤਰ੍ਹਾਂ ਪੁਲਾੜ ਦੀ ਜਟਿਲਤਾ ਵੀ ਲੀਨੀਅਰ ਹੈ.