linear အချိန်အတွက်အရွယ်အစား 3 ၏တစ် ဦး စီထားသောနောက်ဆက်တွဲရှာပါ


ခက်ခဲအဆင့် အလယ်အလတ်
မကြာခဏမေးတယ် Avalara Capital One Citadel Citrix ကို eBay fab မြတ်နိုး
အခင်းအကျင်း

ပြProbleနာဖော်ပြချက်

ပြlinearနာ“ အရွယ်အစား ၃ ၏နောက်ဆက်တွဲရလဒ်ကို linear အချိန်တွင်ရှာပါ” ဟုသင်၌ရှိသည်ဟုဖော်ပြသည် ကိန်း အခင်းအကျင်း။ ပြstatementနာဖြေရှင်းချက်ကဒီနံပါတ်သုံးခုကို [i] <ခင်းကျင်း [k] <array [k] နဲ့ i <j <k ကိုရှာတဲ့နည်းနဲ့ရှာပါမယ်။

နမူနာ

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

ရှင်းလင်းချက်

၂ သည် ၅ ထက်ငယ်သည်၊ ၅ သည် ၇ ထက်ငယ်သည်၊ သူတို့၏အညွှန်းကိန်းများမှာတစ်ခုနှင့်တစ်ခုမတူညီသည်။

algorithm

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 ကိန်း။ ကျနော်တို့ရှာရန်တောင်းဆိုခဲ့ကြသည် စီပြီး ပေးထားသောခင်းကျင်းအတွက်နောက်ဆက်တွဲ။ Sorted နောက်ဆက်တွဲတွင်ကျွန်ုပ်တို့သည်ဂဏန်းသုံးခုပါ ၀ င်သည်။ ကျွန်ုပ်တို့အစဉ်လိုက်စီစဉ်ထားသည်။ ၎င်းသည်အဆက်မပြတ်မဟုတ်ဘဲဆက်တိုက်ဖြစ်ရမည်၊ ပထမနံပါတ်သည်ဒုတိယနံပါတ်ထက်နည်းရမည်၊ ဒုတိယနံပါတ်သည်တတိယနံပါတ်ထက်နည်းရမည်၊ ဒုတိယနှင့်တတိယနိုင်ရန်အတွက်လာသင့်ပါတယ်။

ကျွန်ုပ်တို့သည် array မှ 1 မှ n ထက်လျော့လိမ့်မည်။ ပထမဆုံးနှင့်နောက်ဆုံးအညွှန်း element ကိုချန်ထားလိမ့်မည်။ ဘာလို့လဲဆိုတော့ကျွန်တော်တို့က -1 ကိုသေးငယ်ပြီးကြီးကျယ်သောဖန်တီးထားသည့် Array နှစ်ခုတွင်အမှတ်အသားပြုခဲ့ခြင်းကြောင့်ဖြစ်သည်။ ကျနော်တို့သူတို့ရဲ့ပထမ ဦး ဆုံးအညွှန်း element ကိုအသီးသီးအငယ်နှင့်အကြီး Array ကို၏ -1 နှင့်ညီမျှမှတ်သားခဲ့သည်။ Array ကိုလှည့်ပြီး arr [i] သည် arr [အနည်းဆုံး] ထက်နိမ့်သည်ဖြစ်စေ၊ အနည်းဆုံးဖြစ်စေ 0 ရှိခဲ့သည့်အချက်ကိုစစ်ဆေးပါ၊ အခြေအနေမှန်ကန်ကြောင်းတွေ့ရှိပါကအနိမ့်ဆုံးတန်ဖိုးကို i သို့အဆင့်မြှင့်ပါ၊ ဒြပ်စင် -1 ။

ကျနော်တို့အတူတူပါပဲကျနော်တို့အကြီးအခင်းကျင်းနှင့်အတူပြုကြလိမ့်မည်, ဒါပေမယ့်ညာဘက်အခြမ်း၏ဒုတိယဒြပ်စင်ကနေ 0. မှစစ်ခင်းကျင်း၏ဖြတ်သန်းရာမှအတူ။ ကျနော်တို့ကခင်းကျင်းဖြတ်သန်းနှင့် arr [i] သည် arr [အများဆုံးထက်ကြီးမြတ်သို့မဟုတ်ညီမျှရှိမရှိစစ်ဆေးပါလိမ့်မယ် ] မှန်လျှင်ကျွန်ုပ်တို့အမြင့်ဆုံးတန်ဖိုး 0 နှင့်ကြီးသော [i] -1 သို့မွမ်းမံရန်လိုအပ်သည်။ အခြားအရာများသည်အမြင့်ဆုံးကို [i] အဖြစ်ထားရှိမည်။ ထိုနောက်မှကျွန်ုပ်တို့သည် array ကိုနောက်ကြောင်းပြန်လှည့်ပြီး [i] နှင့်ကြီးသော [i] သည် -1 နှင့်မညီ၊ မမှန်စစ်ဆေးသည်၊ အမှန်ဆိုလျှင်ဖော်ပြပါတန်ဖိုးများကို print ထုတ်ပါလိမ့်မည်။

linear အချိန်အတွက်အရွယ်အစား 3 ၏တစ် ဦး စီထားသောနောက်ဆက်တွဲရှာပါ

 

ကုဒ်

linear အချိန်တွင်အရွယ်အစား 3 ၏ sorted နောက်ဆက်တွဲကိုရှာဖွေ 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

ဂျီနုကုဒ်နံပါတ် (၃) ကိုအချိန်အတိုင်းအတာတစ်ခုစီတွင်ရှာပါ

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” သည် array ထဲရှိ element အရေအတွက်ဖြစ်သည်။ ကျွန်ုပ်တို့သည် array element အားလုံးကိုဖြတ်သန်းသွားသည်။ ပြီးတော့ array ရဲ့အရွယ်အစားက N. ပါ။ အချိန်ရှုပ်ထွေးမှုသည်လည်း linear ဖြစ်သည်။

အာကာသရှုပ်ထွေးမှု

အို (ဎ) ဘယ်မှာ “ n” သည် array ထဲရှိ element အရေအတွက်ဖြစ်သည်။ Array တစ်ခုစီအတွက်သေးငယ်။ ပိုသော element ကိုသိုလှောင်ထားသည်။ ထို့ကြောင့်အာကာသရှုပ်ထွေးလွန်းသည်။