لکیری وقت میں سائز 3 کا ترتیب شدہ تقاضا تلاش کریں


مشکل سطح درمیانہ
اکثر پوچھا جاتا ہے اوالارا کیپٹل ایک درگ Citrix کی ای بے فیب Synopsys
لڑی

مسئلہ یہ بیان

مسئلہ "لکیری وقت میں سائز 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 سے کم کرنے جا رہے ہیں ، ہم پہلا اور آخری انڈیکس عنصر جیسا چھوڑ دیں گے۔ کیونکہ ہم نے ان دو صفوں کو نشان زد کیا ہے جو ہم نے چھوٹے اور بڑے بنائے ہیں۔ ہم نے ان کا پہلا نشان لگایا اور انڈیکس عنصر بالترتیب چھوٹے اور عظیم صفوں کے -1 کے برابر ہے۔ سرے کی سیر کرنا اور جانچ کرنا کہ آیا ارر [i] ارر سے کم یا اس کے برابر ہے [کم سے کم] جہاں کم سے کم ہم 1 کے بطور نشان زد ہوئے ، اگر حالت درست ثابت ہوئی تو کم سے کم i کی قیمت کو اپ ڈیٹ کریں ، اور موجودہ چھوٹی سرنی کو نشان زد کریں۔ عنصر -0.

ایک ہی چیز جو ہم عظیم صف کے ساتھ کریں گے ، لیکن دائیں جانب کے دوسرے عنصر سے صف کے پیچھے صف کی صف 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 ہے۔ وقت کی پیچیدگی بھی لکیری ہوتی ہے۔

خلائی پیچیدگی

اے (ن) کہاں "این" صف میں عناصر کی تعداد ہے۔ ہم ہر صف عنصر کے ل the چھوٹے اور زیادہ عنصر کو ذخیرہ کرتے رہے ہیں۔ اس طرح خلائی پیچیدگی بھی لکیری ہوتی ہے۔