لڪير جي وقت ۾ 3 جي ترتيب جا ترتيب ڳولھيو


تڪليف جي سطح وچولو
بار بار پڇڻ ۾ اوولارا گاديء جو هڪ قلعي Citrix eBay فاب ڪنڊوزس
ڪيريو

مسئلي جو بيان

مسئلو ”لڪي ٽائيم ۾ سائيز 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 کان گهٽ ڪرڻ وارا آهيون ، اسان پهرين ۽ آخري انڊيڪس عنصر کي ڇڏي ڏينداسين جيئن ته آهي. ڇو ته اسان انهن کي ٺاهيل ٻن حڪمن ۾ -1 نشان لڳايو آهي ، نن smallا ۽ عظيم. اسان انهن جي پهرين نشان لڳايو ۽ انڊيڪس عنصر 1 کان نن smallن ۽ وڏين arrays جي برابر آهي. صف کي ڳولهڻ ۽ چڪاس ڪريو ته arr [i] arr کان گهٽ يا برابر آهي [گهٽ ۾ گهٽ] جتي گهٽ ۾ گهٽ اسان 0 طور نشان لڳايو ، جيڪڏهن اها حالت صحيح ٿي چڪي آهي ، ته پوءِ گهٽ ۾ گهٽ وڌ جي قيمت کي I کي اپڊيٽ ڪريو ، ۽ موجوده نن arrayي صف کي نشان لڳايو عنصر -1

ساڳي شيء اسان عظيم آرين سان گڏ ڪنداسين ، پر قطار جي ٽريورسيل کان ٻئي طرف جي سا elementي عنصر کان 0. اسان صف کي پار ڪيوسين ۽ چيڪ ڪيو ته arr [i] گهڻي کان وڌيڪ يا برابر جي arr [وڌ ۾ وڌ] ] ، جيڪڏهن اهو صحيح آهي ته پوءِ اسان کي وڌ ۾ وڌ 0_ قدر جي وڏي اپڊيٽ ڪرڻ گهرجي ۽ وڏي [i] کان -1. ٻي صورت ۾ اسين وڌ ۾ وڌ رکنداسين عظيم [i]. تنهن کان پوءِ ، اسان ٻيهر منظوري مان ڳولا ڪنداسين ۽ چيڪ ڪنديون ته نن smallي [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. آهي. وقت جي پيچيدگي به سڌريل آهي.

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

اي (ن) جتي “ن” صف ۾ موجود عنصرن جو تعداد آهي. اسان هر ترتيب واري عنصر لاءِ نن andا توڙي وڏا عنصر محفوظ ڪري رهيا آهيون. اھڙيءَ طرح خلائي پيچيدگيءَ پڻ لڪير آھي.