K විශේෂිත අංක සහිත කුඩාම සුබාරේ


දුෂ්කරතා මට්ටම Hard
නිතර අසනු ලැබේ ඇමේසන් ගූගල්
අරා හැෂ් ස්ලයිඩින් කවුළුව පොයින්ටර් දෙකක්

ඔබට පූර්ණ සංඛ්‍යාවක් ඇතැයි සිතමු අරාව සහ අංක k. ගැටළු ප්‍රකාශය මඟින් කුඩාම උප-අරාව (l, r) ද ඇතුළුව සොයා ගැනීමට අසයි, ඒ ආකාරයෙන් එම කුඩාම උප-අරාව තුළ හරියටම k විශේෂිත සංඛ්‍යා ඇත.

උදාහරණයක්

ආදානය:

{1, 2, 2, 3, 4, 5, 5}

k = 3

ප්රතිදාන:

2, 4

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

{2, 3, 4} යනු 2 සිට ආරම්භ වන කුඩාම උප-අරාවයිnd දර්ශකය 4 දක්වාth k සමඟ දර්ශකය, එනම් විශේෂිත මූලද්‍රව්‍ය 3 ක්.

ආදානය:

{2, 5, 6, 7}

k = 2

ප්රතිදාන:

2, 3

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

Index 2, 5} යනු 2 වන දර්ශකයේ සිට 3 වන දර්ශකය දක්වා ආරම්භ වන කුඩාම උප-අරාවයි.

ඇල්ගොරිතම

  1. පැහැදිලි මූලද්‍රව්‍යය 0 ලෙසත් වම් පැත්ත සහ දකුණු පැත්තේ දර්ශක -1 ලෙසත් සකසන්න.
  2. අරාව හරහා ගමන් කරන්න,
  3. ලබා දී ඇති අංක k ට වඩා වෙනස් මූලද්‍රව්‍ය කිසිවක් නොමැති නම් දකුණු පැත්ත 1 කින් වැඩි කිරීම,
  4. ඉන්පසු ගණනය වැඩි කර අරාව මූලද්‍රව්‍යයේ සංඛ්‍යාතය ගබඩා කරන්න සිතියම.
  5. විශේෂිත මූලද්‍රව්‍යයන් ලබා දී ඇති අංකයට සමාන වන අතර එසේ සාදන ලද දිග කලින් යාවත්කාලීන කළ දිගට වඩා කුඩා නම්, වම් සහ දකුණු පැත්තේ දර්ශකයන් සහ කැඩී යයි.
  6. K ට වඩා අඩු මූලද්‍රව්‍ය ගණන සොයාගතහොත් බිඳී යන්න.
  7. K ට සමාන මූලද්‍රව්‍ය ගණන k ට සමාන දැයි පරීක්ෂා කරන්න, ඉන්පසු දකුණු පැත්තේ දර්ශක වැඩි කරන්න.
  8. විශේෂිත මූලද්‍රව්‍යයන් ලබා දී ඇති අංකයට සමාන වන අතර එසේ සාදන ලද දිග කලින් යාවත්කාලීන කළ දිගට වඩා කුඩා නම්, වම් සහ දකුණු පැත්තේ දර්ශකයන් සහ කැඩී යයි.
  9. මූලද්රව්යයේ සංඛ්යාතය 1 ක් දැයි සොයා බලන්න, ඉන්පසු සිතියමෙන් එම මූලද්රව්යය ඉවත් කරන්න, එසේ නොමැති නම් එම මූලද්රව්යයේ සංඛ්යාතය ගණනය කිරීම අඩු කරන්න
  10. වම් පැත්තේ දර්ශකය 0 හා දකුණු පැත්ත n ට සමාන බව සොයාගතහොත් එයින් අදහස් වන්නේ එය අවලංගු බවයි.
  11. නැතහොත්, වම් පැත්ත සහ දකුණු පැත්තේ අගයන් මුද්‍රණය කරන්න.

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

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

සිතියමක ප්‍රමාණය k ට වඩා අඩු නම්, කැඩී යන්න. අපට සිතියමක අගයන් ඇත. සිතියමේ ප්‍රමාණය k ට සමාන වන තෙක් ලූපය ඉදිරියට යනු ඇත, සිතියමක අරාව මූලද්‍රව්‍යයේ සංඛ්‍යාතය 1 ට සමාන බව සොයා ගනී, එවිට අපි එම විශේෂිත මූලද්‍රව්‍යය සිතියමෙන් ඉවත් කළ යුතුය, එසේ නොමැතිනම් අපි අඩු කළ යුතුය සිතියමකින් එම විශේෂිත මූලද්‍රව්‍යයේ සංඛ්‍යාතය. නැවතත් අපි සිතියමෙහි විශාලත්වය k ට සමානද යන්න සහ වර්තමාන උප-අරාවෙහි දිග කලින් යාවත්කාලීන කළ දිගට වඩා අඩුද යන්න පරීක්ෂා කර බැලීමට යන්නේ නම්, වම් පැත්ත සහ දකුණු පැත්තේ දර්ශක යාවත්කාලීන කරන්න. අරාව මූලද්‍රව්‍යයේ සංඛ්‍යාතය 1 නම්, එම මූලද්‍රව්‍යය ඉවත් කර වෙනත් මූලද්‍රව්‍යයක සංඛ්‍යාතය අඩු කරන්න.

අරාවෙහි ගමන් කිරීමෙන් පසු, වම් පැත්තේ දර්ශකය 0 සහ දකුණු පැත්තේ දර්ශකය n දක්වා තිබේ නම්, එයින් අදහස් වන්නේ එය අවලංගු k ය. කුඩාම උප අරාවෙහි ආරම්භක ලක්ෂ්‍යය සහ අවසාන ලක්ෂ්‍යය වන වම් සහ දකුණු පැත්තේ දර්ශකයේ අගය මුද්‍රණය කරන්න.

ක්රියාත්මක කිරීම

K විශේෂිත අංක # සහිත කුඩාම සබ්රේ සඳහා C ++ වැඩසටහන ඇතුළත් වේ

#include<map>

using namespace std;

void getSmallestSubarray(int arr[], int n, int k)
{
    int left = 0, right = n;
    int j = -1;
    map<int, int> MAP;
    for (int i=0; i<n; i++)
    {
        while (j < n)
        {
            j++;
            if (MAP.size() < k)
                MAP[arr[j]]++;

            if (MAP.size() == k && ((right - left) >= (j - i)))
            {
                left = i;
                right = j;
                break;
            }

        }
        if (MAP.size() < k)
            break;

        while (MAP.size() == k)
        {
            if (MAP[arr[i]] == 1)
                MAP.erase(arr[i]);
            else
                MAP[arr[i]]--;

            i++;

            if (MAP.size() == k && (right - left) >= (j - i))
            {
                left = i;
                right = j;
            }
        }
        if (MAP[arr[i]] == 1)
            MAP.erase(arr[i]);
        else
            MAP[arr[i]]--;
    }
    if (left == 0 && right == n)
        cout << "Invalid k" << endl;
    else
        cout << left << " " << right;
}
int main()
{
    int arr[] = {1, 2, 2, 3, 4, 5, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    getSmallestSubarray(arr, n, k);
    return 0;
}
2 4

K විශේෂිත අංක සහිත කුඩාම සුබාරේ සඳහා ජාවා වැඩසටහන

import java.util.HashMap;
import java.util.Map;
class smallestSubArray
{
    public static void getSmallestSubarray(int arr[], int n, int k)
    {
        int left = 0, right = n;
        int j = -1;
        HashMap<Integer, Integer> MAP=new HashMap<>();
        for (int i=0; i<n; i++)
        {
            while (j < n-1)
            {
                j++;
                if (MAP.size() < k)
                {

                    if(MAP.containsKey( arr[j] ))
                        MAP.put( arr[j], MAP.get( arr[j] ) + 1 );
                    else
                        MAP.put(arr[j],1);
                }

                if (MAP.size() == k && ((right - left) >= (j - i)))
                {
                    left = i;
                    right = j;
                    break;
                }
            }
            if (MAP.size() < k)
                break;

            while (MAP.size() == k)
            {
                if (MAP.get(arr[i]) == 1)
                    MAP.remove(arr[i]);
                else
                    MAP.put(arr[i], MAP.get(arr[i])-1);

                i++;

                if (MAP.size() == k && (right - left) >= (j - i))
                {
                    left = i;
                    right = j;
                }
            }
            if (MAP.get(arr[i]) == 1)
                MAP.remove(arr[i]);
            else
                MAP.put(arr[i], MAP.get(arr[i])-1);
        }
        if (left == 0 && right == n)
            System.out.println("Invalid k");
        else
            System.out.println(left+" "+right);
    }
    public static void main(String [] args)
    {
        int arr[] = {1, 2, 2, 3, 4, 5, 5};
        int n = arr.length;
        int k = 3;
        getSmallestSubarray(arr, n, k);

    }
}
2 4

K විශේෂිත අංක සහිත කුඩාම සබ්රේ සඳහා සංකීර්ණතා විශ්ලේෂණය

කාල සංකීර්ණත්වය

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

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

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