အရှည်ဆုံးတိုးလာသည့်နောက်ဆက်တွဲတည်ဆောက်မှု (N log N)


ခက်ခဲအဆင့် ခိုင်မာသော
မကြာခဏမေးတယ် အမေဇုံ ဘဏ် Paytm Samsung
အခင်းအကျင်း Binary Search Dynamic Programming

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

မင်းကိုပေးထားတယ် အခင်းအကျင်း of ကိန်း။ ပြLongနာက“ အရှည်ဆုံးတိုးမြှင့်ခြင်းနောက်ဆက်တွဲတည်ဆောက်ခြင်း (N log N)” ပြproblemနာကအရှည်ဆုံးတိုးပွားမှုနောက်ဆက်တွဲကိုတည်ဆောက်ရန်တောင်းဆိုသည်။

နမူနာ

arr[]={1, 4, 7, 2, 9, 6, 12, 3 }
12, 9, 7, 4, 1 and the size of this longest increasing subsequence is 5.

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

ကျနော်တို့က array ထဲမှာတိုးပွားလာသောအရှည်ဆုံးနောက်ဆက်တွဲထွက်ရှာပါ။

အရှည်ဆုံးတိုးလာသည့်နောက်ဆက်တွဲတည်ဆောက်မှု (N log N)

အရှည်ဆုံးတိုးလာသည့်နောက်ဆက်တွဲတည်ဆောက်မှုအတွက် Algorithm (N log N)

1. Create two arrays lastIndexes and firstIndexes of size n, and initialize both of the arrays with 0 and -1 respectively.
2. Traverse the array from 1 to n(length of the array).
  1. Check if the current array element is less than the arr[lastIndexes[0]], if true, then update lastIndexes[0]=1.
  2. Check if the arr[i] is greater than the arr[lastIndexes[leng-1]], do the following
    1. Set the firstIndexes[i] to lastIndexes[leng-1].
    2. lastIndexes[leng++] = i.
  3. Else get the position of arr[i] using binary search and do the following.
    1. Update the value at firstIndexes[i] to lastIndexes[position-1].
    2. Update the value of the lastIndexes[position] to i.
3. Print the array, by initializing the value of i to the firstIndexes[i].

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

ကျနော်တို့ကိန်းဂဏန်းများကိုခင်းကျင်းပေးပြီးဆောက်လုပ်ဖို့တောင်းဆိုခဲ့တယ် အရှည်ဆုံးတိုးပွားလာနောက်ဆက်တွဲ။ ၎င်းအတွက် lastIndexes နှင့် firstIndexes နှစ်ခုကို အသုံးပြု၍ 0 နှင့် -1 တန်ဖိုးအသီးသီးကိုအသုံးပြုလိမ့်မည်။ firstIndexes ခင်းကျင်းခြင်းကို 1 အဖြစ်အစပြုလိမ့်မည်။ array ကိုဖြတ်သန်းစဉ်တန်ဖိုးများကိုကျွန်ုပ်တို့ update လုပ်ပါမည်။

1 ကနေ n အထိခင်းကျင်းသွားလိမ့်မယ်။ n သည်ခင်းကျင်း၏အရှည်ဖြစ်သည်။ ဖြတ်သန်းသွားနေစဉ်, array lastIndexes တစ်ခုခင်းကျင်း၏အနေအထားသို့မဟုတ်အညွှန်းကိန်းအဖြစ်အသုံးပြုလိမ့်မည်။ ကျနော်တို့လက်ရှိ array element ကို lastIndexes [leng-1] ၏ array ထက်လျော့နည်းခြင်းရှိမရှိစစ်ဆေးမယ့်အခြေအနေအချို့ကိုစစ်ဆေးပါလိမ့်မယ်။ အရှည်ကိုကန ဦး 1 အဖြစ်သတ်မှတ်တယ်။ ဆိုလိုတာကအနည်းဆုံးအရှည် ၁ မှာရှိလိမ့်မယ်။ ဒါကြောင့်အထက်ပါအခြေအနေမှန်ကန်တယ်ဆိုရင် lastIndexes [1] ကို 0 သို့မွမ်းမံပါ။

arr [i] သည် lastIndexes [n-1] ၏ array ထက်ကြီးမြတ်သည်ကိုစစ်ဆေးရန်လိုသည်။ ပြီးရင် arrays နှစ်ခုစလုံးကို update လုပ်ပါ။ firstIndexes [i] ကို lastIndexes ၏နောက်ဆုံးတန်ဖိုး [n-1] နှင့် lastIndexes [leng] ကို i ထားလိုက်ပါ။ Leng တန်ဖိုးကိုတိုးပါ။ ကျန်ရှိနေသေးသောကျွန်ုပ်တို့သည်လက်ရှိ array element ကိုအနေအထားကိုရှာဖွေရန်ရှိသည်။ ဒီအတွက်ငါတို့ binary search ကိုသုံးပြီးဒီ index ကို position ထဲကိုရောက်သွားလိမ့်မယ်။ ပြီးတော့ lastIndexes [position-1] ၏တန်ဖိုးကို firstIndexes [i] နှင့် lastIndexes [position] ကို i သို့ပြောင်းပါ။

traversal ပြီးနောက် array ကို print ထုတ်ရန်လိုအပ်သည်။ ဒီအတွက်ကျွန်တော်တို့ဟာနောက်ဆုံးကနေ 0 အထိဖြတ်သွားပါလိမ့်မယ်th တိုင်းဖြတ်သန်းပြီးနောက် [i] firstIndexes ဖို့အညွှန်းကိန်းတစ်ခုချင်းစီကိုနေရာချခြင်းနှင့်ခင်းကျင်း၏တစ်ခုချင်းစီကိုဖြစ်နိုင်သမျှတန်ဖိုးကို print ထုတ်။

ကုဒ်

အရှည်ဆုံးတိုးပွားမှုနောက်ဆက်တွဲတည်ဆောက်မှုအတွက် C ++ ကုဒ် (N log N)

#include<iostream>
#include<vector>

using namespace std;

int GetPosition(int arr[], vector<int>& T, int left, int right,int key)
{
    while (right - left > 1)
    {
        int mid = left + (right - left) / 2;
        if (arr[T[mid]] >= key)
            right = mid;
        else
            left = mid;
    }
    return right;
}
int LongestIncreasingSubsequence(int arr[], int n)
{
    vector<int> lastIndexes(n, 0);
    vector<int> firstIndexes(n, -1);

    int len = 1;
    for (int i = 1; i < n; i++)
    {
        if (arr[i] < arr[lastIndexes[0]])
        {
            lastIndexes[0] = i;
        }
        else if (arr[i] > arr[lastIndexes[len - 1]])
        {
            firstIndexes[i] = lastIndexes[len - 1];
            lastIndexes[len++] = i;
        }
        else
        {
            int positon = GetPosition(arr, lastIndexes, -1, len - 1, arr[i]);
            firstIndexes[i] = lastIndexes[positon - 1];
            lastIndexes[positon] = i;
        }
    }
    cout << "Longest Increase Subsequence:" << endl;
    for (int i = lastIndexes[len - 1]; i >= 0; i = firstIndexes[i])
        cout << arr[i] << " ";
    cout << endl;

    cout<<"LIS size:\n";

    return len;
}
int main()
{
    int arr[] = { 1, 4, 7, 2, 9, 6, 12, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);

    cout<< LongestIncreasingSubsequence(arr, n);

    return 0;
}
Longest Increase Subsequence:
12 9 7 4 1
LIS size:
5

အရှည်ဆုံးတိုးခြင်း၏နောက်ဆက်တွဲတည်ဆောက်ခြင်းအတွက် Java ကုဒ် (N log N)

import java.util.Arrays;

class LongestIncreasingSubsequence
{
    public static int GetPosition(int arr[], int T[], int left, int right, int key)
    {
        while (right - left > 1)
        {
            int mid = left + (right - left) / 2;
            if (arr[T[mid]] >= key)
                right = mid;
            else
                left = mid;
        }
        return right;
    }
    public static int getSubsequence(int arr[], int n)
    {
        int lastIndexes[] = new int[n];

        Arrays.fill(lastIndexes, 0);

        int firstIndexes[] = new int[n];

        Arrays.fill(firstIndexes, -1);

        int len = 1;

        for (int i = 1; i < n; i++)
        {
            if (arr[i] < arr[lastIndexes[0]])
                lastIndexes[0] = i;
            else if (arr[i] > arr[lastIndexes[len - 1]])
            {
                firstIndexes[i] = lastIndexes[len - 1];
                lastIndexes[len++] = i;
            }
            else
            {
                int positon = GetPosition(arr, lastIndexes, -1, len - 1, arr[i]);
                firstIndexes[i] = lastIndexes[positon - 1];
                lastIndexes[positon] = i;
            }
        }
        System.out.println("Longest Increasing Subsequence of given input");
        for (int i = lastIndexes[len - 1]; i >= 0; i = firstIndexes[i])
            System.out.print(arr[i] + " ");

        System.out.println();

        return len;
    }
    public static void main(String[] args)
    {
        int arr[] = { 1, 4, 7, 2, 9, 6, 12, 3 };
        int n = arr.length;

        System.out.print("LIS size:\n" + getSubsequence(arr, n)+"\n");
    }
}
Longest Increasing Subsequence of given input
12 9 7 4 1
LIS size:
5

 

ရှုပ်ထွေးဆန်းစစ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (n log n) "n" သည် array အတွင်းရှိ element အရေအတွက်ဖြစ်သည်။ ကျွန်တော်တို့ဟာ logarithmic factor ပေးတဲ့ binary search ကိုသုံးပြီးကတည်းက။ ဒါပေမယ့် index တစ်ခုစီအတွက် binary search ကိုခေါ်ရမယ်။ အဆိုးဆုံးအနေဖြင့်အချိန်ရှုပ်ထွေးမှုသည် O (N log N) ဖြစ်သည်။

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

အို (ဎ) "n" သည် array အတွင်းရှိ element အရေအတွက်ဖြစ်သည်။ ကျွန်ုပ်တို့သည် firstIndexes နှင့် lastIndexes များကိုယာယီ Array နှစ်ခုဖန်တီးပြီးဖြစ်သည်။ အဆိုပါအာကာသရှုပ်ထွေးဖြစ်လာသည် အို (N).