တဆက်တည်းဒြပ်စင်နှင့်အတူအကြီးဆုံး subarray ၏အရှည်


ခက်ခဲအဆင့် အလယ်အလတ်
မကြာခဏမေးတယ် Adobe က အမေဇုံ ဘလွန်းဘာ့ဂ် Cisco သည် ကရာတေး Monotype Solutions Paytm PayU Publicis Sapient SAP Labs
အခင်းအကျင်း hash

ပြ “နာ က“ တဆက်တည်းပါ ၀ င်သောအကြီးဆုံး subarray ၏အရှည်” သည်သင့်အားပေးထားသည်ဟုဖော်ပြသည် ကိန်း အခင်းအကျင်း။ အဆိုပါပြstatementနာကြေညာချက်အစဉ်အဆက် (စဉ်ဆက်မပြတ်တက်, သို့မဟုတ်ကဆင်းဖြစ်စေ) element တွေကိုတစ် ဦး sequence ကိုအတွက်စီစဉ်နိုင်သည့်အရှည်ဆုံးတဆက်တည်း Sub- ခင်းကျင်း၏အရှည်ထွက်ရှာတွေ့မှမေးတယ်။ array ထဲတွင်နံပါတ်များကိုအကြိမ်များစွာတွေ့နိုင်သည်။

နမူနာ

တဆက်တည်းဒြပ်စင်နှင့်အတူအကြီးဆုံး subarray ၏အရှည်

arr[] = {10, 12, 13, 11, 8, 10, 11, 10}
4

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

0th index မှ 3 index အထိနံပါတ် 10, 12, 13, 11 ပါ ၀ င်သည်။ ၁၀၊ ၁၁၊ ၁၂၊ ၁၃ တွင်အရှည် ၄ ဖြစ်လာသည်။

arr[] = {1, 1, 3, 2, 8, 4, 8, 10}
3

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

ပထမအညွှန်းမှ ၃ အညွှန်းအထိနံပါတ် ၁၊ ၃၊ ၂ ကိုထုံးစံအတိုင်း ၁၊ ၂၊ ၃ အတိုင်းအတာဖြင့်စီစဉ်နိုင်သည်။

algorithm

  1. အစုံ maxLength 1 သို့။
  2. i <0၊ i <l -1 နေစဉ် loop တစ်ခုကိုဖွင့်ပါ။
    1. a) ကြေညာပါ အစုံ နှင့်သတ်မှတ်မည်သို့ arr [i] ထည့်ပါ။
    2. ၏တန်ဖိုးသတ်မှတ်မည် maxlen နှင့် minlen ဆိုက်ရောက်ရန် [i] ။
    3. j = l ကို၎င်း၊ j = l ကို၎င်း၊
      1. Set တွင် arr [j] တန်ဖိုးရှိမရှိစစ်ဆေးပါ။
        1. မှန်ရင်ချိုးပါ။
        2. ကျန်သော
          1. Set [j] ကို Set ထဲထည့်ပါ။
          2. minlen နှင့် arr [j] ကြားရှိနိမ့်ဆုံးကိုရှာ။ ၎င်းကို minlen သို့သိမ်းထားပါ။
          3. maxlen နှင့် arr [j] ကြားရှိအမြင့်ဆုံးကိုရှာဖွေ။ ၎င်းကို maxlen သိုလှောင်ထားပါ။
          4. maxlen-min = = ညလျှင်စစ်ဆေးပါ - ငါ
            1. အမှန်ဖြစ်ပါက maxLength နှင့် max-minlen +1 အမြင့်ဆုံးကိုရှာဖွေ။ ၎င်းကို maxLength သိုလှောင်ထားပါ။
  3. maxLength သို့ပြန်သွားပါ။

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

ကျွနု်ပ်တို့ကိုနံပါတ်စဉ်များပါ ၀ င်သည့်အရှည်ဆုံးဆက်တိုက်အကျဆုံးအရှည်အားရှာဖွေရန်ကျွန်ုပ်တို့အားမေးသောမေးခွန်းတစ်ခုကိုကျွန်ုပ်တို့အားပေးခဲ့သည်။ ပေးထားသောခင်းကျင်းချက်တွင်ထပ်တူနံပါတ်များရှိနိုင်သည်။ ဒီအဖြစ်အပျက်ကိုငါတို့ကောင်းစွာကိုင်တွယ်ရမယ်။ အဖြေရရန်ကျွန်ုပ်တို့သည် a ကိုသုံးမည် အစုံ နှင့်ထပ်တူ element တွေကိုဂရုစိုက်လိမ့်မည်ဟုတစ် ဦး အသိုက် loop ကို။

ဥပမာတစ်ခုကိုသုံးသပ်ကြည့်ကြစို့။

နမူနာ

ဆိုက်ရောက် [] = {10, 12, 13, 11, 8, 10}

ကျွန်ုပ်တို့သည်ကွင်းဆက်တစ်ခုကိုဖွင့်ပြီးနောက် Set ကိုအသုံးပြုပြီးနံပါတ်တစ်ကိုတစ်ကြိမ်ထည့်ပြီး maxlen နှင့် minlen ၏တန်ဖိုးကို arr ပြုလုပ်ပါလိမ့်မည်။ နောက်တစ်ခုက element တစ်ခုကိုရှေ့ကလက်ရှိ element ရဲ့ရှေ့ကနေကွင်းဆင်းသောကွင်းဆက်ကိုဖွင့်ပါ၊ Set တွင် arr [j] ၏တန်ဖိုးပါရှိမရှိစစ်ဆေးပါ၊ element ကိုတွေ့ပါကဖြိုဖျက်ပါ။ နောက်တစ်ခုမှာ arr [j] ၏တန်ဖိုးကို Set ထဲသို့ထည့်ပြီး maxlen နှင့် arr [j] အကြားရှိအမြင့်ဆုံးနှင့် minlen နှင့် arr [j] အကြားအနိမ့်ဆုံးကိုရှာ။ ၎င်းကို maxlen နှင့် minlen သို့သိမ်းထားပါ။ maxlen-min သည် ji နှင့်ညီမျှမှုရှိမရှိစစ်ဆေးပါ၊ ထို့နောက် maxLength ၏တန်ဖိုးကို update လုပ်ပါ။

maxLength = 1 ။

ကိုယ့် = 0, mySet = {10}, minlen = 10, maxlen = 10

j = i + 1 = 1, အကယ်၍ mySet တွင် 12 ရှိလျှင်၊ မှားသည်။

ထို့ကြောင့် 12 ကို mySet ထဲသို့ထည့်ပါ။ အမြင့်ဆုံး 12 နှင့် 10 ကိုရှာပါ၊ အနိမ့်ဆုံးကို 12 နှင့် maxlen သို့ 10 ကို minlen သို့ရှာပါ။ maxlen-minlen သည် j နှင့်ညီမျှသည်ကိုစစ်ဆေးပါ၊ သို့သော်မှားသည်။

j = 2, အကယ်၍ mySet 13 တွင်ရှိပါကမှားသည်။

ဒါဆို 13 ကို mySet ထဲထည့်ပြီး 13 နဲ့ 12 ကိုရှာပြီး 13 ကို maxlen နဲ့ 10 ကို minlen ထဲမှာထားပါ။ maxlen-minlen j နဲ့ညီလားဆိုတာစစ်ဆေးပါ။ ငါမှားတယ်။

j = 3, အကယ်၍ mySet 11 တွင်ရှိပါကမှားသည်။

ဒါကြောင့် 11 ကို mySet ထဲသို့ထည့်ပါ။ အမြင့်ဆုံး ၁၁ နှင့် ၁၀ ကိုရှာပြီး ၁၃ ကို maxlen သို့ ၁၀ ကို minlen သို့ထည့်ပါ။ maxlen-minlen သည် j နှင့်ညီမျှသည်ကိုစစ်ဆေးပါ။ ၁၃-၁၀ သည် ၃-၀ နှင့်ညီသောကြောင့်ယခုကျွန်ုပ်မှန်ကန်သည်။ ထို့ကြောင့် maxLength နှင့် maxlen-minlen + 11 max (10, 13-10 + 13) အမြင့်ဆုံးကိုရှာဖွေခြင်းအားဖြင့် maxLength ကို update လုပ်ပါ။ ၄ နှင့် ၄ ကို maxLength တွင်သိုလှောင်ထားသည်။ ကတဆက်တည်း Sub- ခင်းကျင်း၏ဤထက်ပိုရှည်အရှည်ကိုတွေ့သည်အထိသတ်မှတ်။

ရလဒ် - ၁၅

ကုဒ်

ကပ်လျက်ဒြပ်စင်များနှင့်အတူအကြီးဆုံး subarray ၏အရှည်ကိုရှာဖွေ C ++ ကုဒ်

#include<set>
#include<iostream>

using namespace std;

int getLongestLength(int arr[], int l)
{
    int maxLength = 1;
    for (int i=0; i<l-1; i++)
    {
        set<int> mySet;
        mySet.insert(arr[i]);
        int minlen = arr[i], maxlen = arr[i];

        for (int j=i+1; j<l; j++)
        {
            if (mySet.find(arr[j]) != mySet.end())
                break;

            mySet.insert(arr[j]);
            minlen = min(minlen, arr[j]);
            maxlen = max(maxlen, arr[j]);

            if (maxlen - minlen == j - i)
                maxLength = max(maxLength, maxlen - minlen + 1);
        }
    }
    return maxLength;
}
int main ()
{
    int arr[] = {10, 12, 13, 11, 8, 10};
    int l = sizeof(arr) / sizeof(arr[0]);
    cout << "Length of the Longest contiguous Sub-Array is: " << getLongestLength(arr, l);
    return 0;
}
Length of the Longest contiguous Sub-Array is: 4

တစ်ဆက်တည်းဒြပ်စင်များနှင့်အတူအကြီးဆုံး subarray ၏အရှည်ကိုရှာဖွေ Java code ကို

import java.util.HashSet;

class largestSubArrayContiguousElements
{
    public static int getLongestLength(int arr[])
    {
        int l = arr.length;
        int maxLength = 1;

        for (int i=0; i< l-1; i++)
        {
            HashSet<Integer> mySet = new HashSet<>();
            mySet.add(arr[i]);

            int min = arr[i];

            int max = arr[i];

            for (int j=i+1; j<l; j++)
            {
                if (mySet.contains(arr[j]))
                    break;

                mySet.add(arr[j]);
                min = Math.min(min, arr[j]);
                max = Math.max(max, arr[j]);

                if (max-min == j-i)
                    maxLength = Math.max(maxLength, max-min+1);
            }
        }
        return maxLength;
    }
    public static void main (String[] args)
    {
        int arr[] = {10, 12, 13, 11, 8, 10};
        System.out.println("Length of the Longest contiguous SubArray is: "+getLongestLength(arr));
    }
}
Length of the Longest contiguous SubArray is: 4

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

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

အို (။2) ဘယ်မှာ “ n” သည် array အတွင်းရှိ element အရေအတွက်ဖြစ်သည်။

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

အို (ဎ) ဘယ်မှာ “ n” သည် array အတွင်းရှိ element အရေအတွက်ဖြစ်သည်။