ትንሹ ንዑስ ቡድን ከ k የተለዩ ቁጥሮች ጋር


የችግር ደረጃ ጠንካራ
ውስጥ በተደጋጋሚ ተጠየቀ አማዞን google
ሰልፍ ሃሽ የተንሸራታች መስኮት ሁለት ጠቋሚ

ኢንቲጀር አለህ እንበል ደርድር እና አንድ ቁጥር ኬ. የችግሩ መግለጫ አነስተኛውን የክልል ንዑስ ንዑስ ክፍልን (l ፣ r) ን በአጠቃላይ እንዲያካትት ይጠይቃል ፣ በእንደዚህ ዓይነት መንገድ በዚያ አነስተኛ ንዑስ ክፍል ውስጥ በትክክል የተካተቱ ልዩ ቁጥሮች አሉ ፡፡

ለምሳሌ

ግቤት

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

k = 3

ውጤት

2, 4

ማብራሪያ:

{2, 3, 4} ከ 2 ጀምሮ ትንሹ ንዑስ ድርድር ነውnd መረጃ ጠቋሚ እስከ 4th ማውጫ ከ k ማለትም ፣ 3 የተለያዩ አካላት።

ግቤት

{2, 5, 6, 7}

k = 2

ውጤት

2, 3

ማብራሪያ:

{2, 5} ከ 2 ኛ ማውጫ እስከ 3 ኛ ማውጫ የሚጀምረው ትንሹ ንዑስ ድርድር በ k ማለትም ፣ 2 የተለያዩ አካላት ነው ፡፡

አልጎሪዝም

  1. ልዩውን ንጥረ ነገር ወደ 0 እና የግራ ጎን እና የቀኝ የጎን ጠቋሚዎችን ወደ -1 ያዘጋጁ ፡፡
  2. በድርድሩ በኩል ተጓዙ ፣
  3. በቀኝ በኩል በ 1 በመጨመር ፣ ምንም የተለዩ አባሎች ከሌሉ ከተጠቀሰው ቁጥር k ያነሰ ከሆነ ፣
  4. ከዚያ ቆጠራውን ይጨምሩ እና የድርድር አባላትን ድግግሞሽ ወደ ውስጥ ያከማቹ ካርታ.
  5. የተለዩ አካላት ከተሰጠው ቁጥር k ጋር እኩል ከሆኑ እና የተሰራው ርዝመት ከዚህ በፊት ከተዘመነው ርዝመት ያነሰ ከሆነ ፣ ከዚያ የግራ እና የቀኝ የጎን ጠቋሚዎችን እና ይሰብሩ ፡፡
  6. የተለዩ አባሎች ብዛት ከ k ያነሰ ሆኖ ከተገኘ ከዚያ ይሰብራል።
  7. የተለዩ አባሎች ብዛት ከ k ጋር እኩል ሆኖ የተገኘ መሆኑን ያረጋግጡ ፣ ከዚያ የቀኝ የጎን ጠቋሚዎችን ይጨምሩ ፡፡
  8. የተለዩ አካላት ከተሰጠው ቁጥር k ጋር እኩል ከሆኑ እና የተሰራው ርዝመት ከዚህ በፊት ከተዘመነው ርዝመት ያነሰ ከሆነ ፣ ከዚያ የግራ እና የቀኝ የጎን ጠቋሚዎችን እና ይሰብሩ ፡፡
  9. የንጥሉ ድግግሞሽ 1 ሆኖ ከተገኘ ያረጋግጡ ፣ ከዚያ ያንን ንጥረ ነገር ከካርታው ላይ ያስወግዱ ፣ ከዚያ የዚያን ንጥረ ነገር ድግግሞሽ ብዛት ይቀንሱ
  10. የግራ በኩል ጠቋሚው 0 እና የቀኝ ጎኑ ከ n ጋር እኩል ሆኖ ከተገኘ ዋጋ የለውም ማለት ነው ፡፡
  11. ሌላ ፣ የግራውን እና የቀኝ የጎን እሴቶችን ያትሙ።

ማስረጃ

ድርድሩን በሚያልፉበት ጊዜ እያንዳንዱን የድርጅት አካላት ድግግሞሽ ያከማቹ ፣ እና እያንዳንዱን የድርድር አካል ይምረጡ ፣ እና የዚያ ድርድር አባል ድግግሞሽ ለመቁጠር እና ለማከማቸት ከፈለግነው የካርታ መጠን ከ k ያነሰ ከሆነ ያረጋግጡ። የካርታ መጠን ኬኖች (የተለዩ አባል ቁጥር) እና እንዲሁም የአሁኑ ርዝመት ከቀዳሚው ንዑስ-ረድፍ የቀደመ ርዝመት ያነሰ ነው ፣ ከዚያ የግራውን እና የቀኝ የጎን አመልካቾችን እናዘምነዋለን። መላው ካርታ አንድ ጊዜ እስኪያልፍ ድረስ ይህ ሁሉ በክብ ውስጥ ይሄዳል።

የካርታ መጠን ከ k ያነሰ ሆኖ ከተገኘ ከዚያ ይሰብሩ። እሴቶቹን በካርታ ላይ አግኝተናል ፡፡ ሉፕ ከ k ጋር እኩል ሆኖ እስከ ተገኘው የካርታ መጠን ድረስ ይሄዳል ፣ በካርታ ውስጥ ያለው የድርድር ንጥረ ነገር ድግግሞሽ ከ 1 ጋር እኩል ሆኖ ተገኝቷል ፣ ከዚያ ያንን የተወሰነ አካል ከካርታው ላይ ማስወገድ ያስፈልገናል ፣ አለበለዚያ እኛ መቀነስ አለብን የዚያ የተወሰነ አካል ድግግሞሽ ከካርታ። እንደገና የካርታ መጠኑ ከ k ጋር እኩል መሆኑን እና የአሁኑ ንዑስ-ድርድር ርዝመት ቀደም ሲል ከተዘመነው ርዝመት ያነሰ መሆኑን እንፈትሻለን ፣ ከዚያ የግራውን እና የቀኝ የጎን ጠቋሚዎችን ያዘምኑ ፡፡ የድርድሩ ንጥረ ነገር ድግግሞሽ 1 ከሆነ ያንን ንጥረ ነገር ያስወግዱ የሌላውን ንጥረ ነገር ድግግሞሽ ይቀንሱ።

ከድርድሩ ከተሻገረ በኋላ የግራው ጠቋሚው 0 እና የቀኝ ጎኑ ጠቋሚ ወደ n ከተገኘ ልክ ያልሆነ k ነው ማለት ነው ፡፡ ሌላኛው የግራ እና የቀኝ ጠቋሚውን እሴት ያትሙ ፣ ይህም የትንሹ ንዑስ-ድርድር መነሻ እና መጨረሻ ነጥብ ብቻ ይሆናል።

አፈጻጸም

የ C ++ ፕሮግራም ለትንሹ ንዑስ-መርጃ ከ k ልዩ ቁጥሮች ጋር # ያካትታሉ

#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” በድርድሩ ውስጥ ያሉት ንጥረ ነገሮች ብዛት ነው።