රේඛීය වේලාවේ 3 ප්‍රමාණයේ අනුපිළිවෙලක් සොයා ගන්න


දුෂ්කරතා මට්ටම මධ්යම
නිතර අසනු ලැබේ අවලාරා ප්රාග්ධන එක් සිටඩෙල් Citrix ඊ බේ ෆැබ් 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 ට සමාන බව සලකුණු කළෙමු. අරාව හරහා ගමන් කර අවම [0] ට වඩා අඩු හෝ සමානදැයි පරීක්ෂා කරන්න, එහිදී අප අවම වශයෙන් 1 ලෙස සලකුණු කර ඇති අතර, තත්වය සත්‍ය බව සොයාගත හොත්, අවම අගය i දක්වා යාවත්කාලීන කර වත්මන් කුඩා අරාව සලකුණු කරන්න මූලද්රව්යය -XNUMX සිට.

අපි මහා අරාව සමඟ එකම දේ කරන්නෙමු, නමුත් අරාවෙහි දකුණු පැත්තේ දෙවන මූලද්‍රව්‍යයේ සිට 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 වන බැවින් කාල සංකීර්ණතාව ද රේඛීය වේ.

අභ්‍යවකාශ සංකීර්ණතාව

සාමාන්ය (n) එහිදී “N” යනු අරාවෙහි ඇති මූලද්‍රව්‍ය ගණන වේ. අපි එක් එක් අරාව මූලද්රව්ය සඳහා කුඩා හා විශාල මූලද්රව්ය ගබඩා කර ඇත. මේ අනුව අවකාශයේ සංකීර්ණතාව ද රේඛීය වේ.