පරස්පර මූලද්රව්ය සහිත විශාලතම උපසිරැසි වල දිග


දුෂ්කරතා මට්ටම මධ්යම
නිතර අසනු ලැබේ ඇෙබෝ ඇමේසන් බ්ලූම්බර්ග් සිස්කෝ කරට් මොනෝටයිප් විසඳුම් Paytm PayU ප්‍රසිද්ධයි SAP විද්‍යාගාර
අරා හැෂ්

“පරස්පර මූලද්‍රව්‍ය සහිත විශාලතම උපසිරැසි වල දිග” යන ගැටලුවේ සඳහන් වන්නේ ඔබට ලබා දී ඇති බවයි නිඛිල අරාව. ගැටළු ප්‍රකාශය මඟින් අනුපිළිවෙලකට (අඛණ්ඩ, නැගීම හෝ බැසයාම) මූලද්‍රව්‍ය පිළිවෙලට සකස් කළ හැකි දිගම අනුපූරක උප අරාවේ දිග සොයා ගැනීමට අසයි. අරාවෙහි ඇති සංඛ්‍යා කිහිප වතාවක් සිදුවිය හැක.

උදාහරණයක්

පරස්පර මූලද්රව්ය සහිත විශාලතම උපසිරැසි වල දිග

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

පැහැදිලි කිරීම

0 වන දර්ශකයේ සිට 3 වන දර්ශකය දක්වා අංක 10, 12, 13, 11 අඩංගු වන අතර ඒවා 10, 11, 12, 13 ආකාරයෙන් සකස් කළ හැකි අතර එයින් දිග 4 බවට පත්වේ.

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

පැහැදිලි කිරීම

1 වන දර්ශකයේ සිට 3 වන දර්ශකය දක්වා අංක 1, 3, 2 අඩංගු වන අතර ඒවා 1, 2, 3 ආකාරයෙන් සකස් කළ හැකි අතර එයින් දිග 3 ක් වේ.

ඇල්ගොරිතම

  1. කට්ටලයක් උපරිම දිග 1 දක්වා.
  2. ලූපයක් විවෘත කරන්න, i = 0, මම <l -1,
    1. කට්ටලයක් කට්ටලයට ar [i] එකතු කරන්න.
    2. හි අගය සකසන්න maxlen සහ මිනි වෙත [i].
    3. J = i + 1 සිට ආරම්භ වන අතර, j <l,
      1. Set හි අගය [j] හි තිබේදැයි පරීක්ෂා කරන්න,
        1. ඇත්ත නම්, බිඳ දමන්න.
        2. වෙනත්,
          1. Set [j] සෙට් එකට එක් කරන්න.
          2. මිලේන් සහ ආර් [ජේ] අතර අවම අගය සොයාගෙන එය මිලේන් වෙත ගබඩා කරන්න.
          3. මැක්ස්ලන් සහ ආර් [j] අතර ඇති උපරිමය සොයාගෙන එය මැක්ස්ලෙන් වෙත ගබඩා කරන්න.
          4. Maxlen-min = = j - i දැයි පරීක්ෂා කරන්න
            1. සත්‍ය නම්, උපරිම දිග සහ උපරිම-මිනි +1 අතර උපරිමය සොයාගෙන එය උපරිම දිගට ගබඩා කරන්න.
  3. උපරිම දිග ආපසු එවන්න.

පැහැදිලි කිරීම

අනුපිළිවෙලකට පිළිවෙලට සැකසිය හැකි සංඛ්‍යා කිහිපයක් ඇති දිගම පරස්පර උප-අරාවෙහි දිග සොයා ගැනීමට අසන ප්‍රශ්නයක් අපට ලබා දී ඇත. දී ඇති අරාවෙහි අනුපිටපත් සංඛ්‍යා ඇති බවට නඩුවක් තිබිය හැකිය. අපිත් ඒ නඩුව හැසිරවිය යුතුයි. විසඳුම ලබා ගැනීම සඳහා, අපි a භාවිතා කරනු ඇත කට්ටලයක් සහ අනුපිටපත් මූලද්‍රව්‍ය ගැන සැලකිලිමත් වන කැදැලි පුඩුවක්.

අපි උදාහරණයක් සලකා බලමු:

උදාහරණයක්

අර [] = {10, 12, 13, 11, 8, 10}

අපි ලූපයක් විවෘත කිරීමෙන් පසු කට්ටලයක් භාවිතා කර එකවර අංකයක් එකතු කර මැක්ස්ලන් සහ මිනලන් වල අගය අර [i] ලෙස සකසමු. වත්මන් මූලද්‍රව්‍යයට වඩා එක් මූලද්‍රව්‍යයකින් ආරම්භ වන කැදැලි පුඩුවක් විවෘත කරන්න, මන්ද අපි දැනටමත් වත්මන් මූලද්‍රව්‍යය කට්ටලයට ඇතුළත් කර ඇත්තෙමු. සෙට් එකෙහි ආර් [j] හි අගය තිබේදැයි පරීක්ෂා කරන්න, මූලද්‍රව්‍යය හමු වුවහොත් කැඩී යන්න. වෙනත් ආකාරයකින් අර්‍ [j] හි අගය සෙට් එකට ඇතුළු කර මැක්ස්ලන් සහ ආර් [ජේ] අතර උපරිමය සොයා ගන්න, අවම වශයෙන් මිනලන් සහ ආර් [ජේ] අතර අවම වශයෙන් සොයා ගෙන එය පිළිවෙලින් මැක්ස්ලන් සහ මිනලන් වෙත ගබඩා කරන්න. මැක්ස්ලෙන්-මිනි ජිට සමාන දැයි පරීක්ෂා කරන්න, ඉන්පසු උපරිම දිග යාවත්කාලීන කරන්න.

maxLength = 1.

i = 0, mySet = {10}, minlen = 10, maxlen = 10

j = i + 1 = 1, mySet 12 ක් තිබේ නම් එය අසත්‍යයකි,

එබැවින් මයිසෙට් එකට 12 ක් ඇතුල් කර උපරිම 12 සහ 10 සොයා ගෙන අවම වශයෙන් 12 ක් මැක්ස්ලෙන් සහ 10 ක් මිලේන් ලෙස ගබඩා කර මැක්ස්ලන්-මිලේන් j - i ට සමාන දැයි පරීක්ෂා කරන්න, නමුත් එය අසත්‍යයකි.

j = 2, mySet 13 ක් තිබේ නම් එය අසත්‍යයකි,

එබැවින් 13 ක් mySet තුළට ඇතුළු කර උපරිම 13 සහ 12 සොයාගෙන 13 ක් maxlen හා 10 minlen ලෙස ගබඩා කර maxlen-minlen j ට සමානදැයි පරීක්ෂා කරන්න - i අසත්‍යය.

j = 3, mySet 11 ක් තිබේ නම් එය අසත්‍යයකි,

එබැවින් 11 මයිසෙට් එකට ඇතුළු කර උපරිම 11 සහ 10 සොයාගෙන 13 ක් මැක්ස්ලෙන් සහ 10 මිලේන් ලෙස ගබඩා කර මැක්ලෙන්-මිලේන් ජේ ට සමාන දැයි පරීක්ෂා කරන්න - 13-10 3-0 ට සමාන බැවින් මම දැන් සත්‍යය. එබැවින් උපරිම දිග සහ උපරිම-මිනි + 1 උපරිම (1, 13-10 + 1) සොයා ගැනීමෙන් උපරිම දිග යාවත්කාලීන කරන්න, එය 4 සහ 4 බව සොයාගෙන ඇති අතර එය උපරිම දිගට ගබඩා කර ඇති අතර එය අරාව හරහා ගමන් කරයි පරස්පර උප-අරාවෙහි දිගට වඩා දිගු දිග සොයා ගන්නා තෙක් එය සකසන්න.

නිමැවුම්: 4

කේතය

පරස්පර මූලද්‍රව්‍ය සහිත විශාලතම උපආරසයේ දිග සොයා ගැනීමට 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

පරස්පර මූලද්‍රව්‍ය සහිත විශාලතම සබ්ආරියේ දිග සොයා ගැනීමට ජාවා කේතය

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” යනු අරාවෙහි ඇති මූලද්‍රව්‍ය ගණන වේ.

අභ්‍යවකාශ සංකීර්ණතාව

සාමාන්ය (n) එහිදී “N” යනු අරාවෙහි ඇති මූලද්‍රව්‍ය ගණන වේ.