በመለኪያ መስኮቱ ሁሉ የተለዩ ንጥረ ነገሮችን ይቆጥሩ ኬ  


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

ንዑስ ክፍልፎች አሁን ለተወሰነ ጊዜ የምንተጋበት ነገር ናቸው ፡፡ ባለፈው የትዕይንት ክፍል እኛ ማድረግ የምንችላቸውን ንዑስ ቁጥሮች በተለየ ቁጥሮችን እንኳን ሸፍነናል ፡፡ በዚህ ጊዜ በእያንዳንዱ ኬ መጠን ውስጥ በእያንዳንዱ መስኮት ውስጥ ልዩ አባሎችን እንቆጥራለን ፡፡

ክፍል -1  

ስለ ችግሩ ፡፡

ያልተመደቡ የቁጥር ቁጥሮች ተሰጠ። እያንዳንዱ ንዑስ ንዑስ ቁጥር ያላቸውን ልዩ የቁጥር ቁጥሮች ለማወቅ ነው። መግለጫውን ከናሙና የሙከራ ጉዳይ ጋር እንፈትሽ ፡፡

የተሰጠው

ድርድር: {1,2,3,4,4,2,3}

የንዑስ ክፍሎች መጠን: 4

ሊሆኑ የሚችሉ ንዑስ ክፍሎች ሊሆኑ ይችላሉ

1,2,3,4 {}

2,3,4,4 {}

3,4,4,2 {}

4,4,2,3 {}

ከላይ በተጠቀሱት ንዑስ ክፍሎች ውስጥ ያሉት ልዩ ቁጥሮች

4,3,2 እና 3

ክፍል -2  

ወደ ችግሩ መቅረብ የምንችልባቸው ብዙ መንገዶች አሉ ፡፡ ግን ከቀሩት ውስጥ በጣም ጥሩውን በሚሆነው ላይ እወያያለሁ ፡፡ ንዑስ ንዑስ ክፍሎችን ስመዝ አድማጮቼ አንድ ንድፍ ያስተውሉ ነበር ፡፡ ለእያንዳንዱ መስኮት የ k መጠን ለማቆየት አዲስ ንጥረ ነገር ስናክል ከመጨረሻው መስኮት የመጀመሪያውን ንጥረ ነገር እንተወዋለን ፡፡

በሂደቱ አንድ በአንድ እንሂድ

  • በመጀመሪያ ፣ የመጀመሪያውን መስኮት ሁሉንም ንጥረ ነገሮች ለማሳለፍ የ k loop ን ያሂዱ
  • ሁሉንም ንጥረ ነገሮች በ HashMap ይቆጥሩ
  • ቁልፉ እሴቱ ያለው ንጥረ-ነገር በሃሽ ማፕ ውስጥ የሚከሰትባቸው ጊዜያት ብዛት ነው
  • ወደ ፊት ስንሄድ የመጀመሪያውን ንጥረ ነገር ከሃሽ ማፕ እናወጣለን
  • ንጥረ ነገሩ በቀላሉ ካስወገድነው አንድ ጊዜ ብቻ ከተከሰተ
  • በሌላ በኩል ደግሞ በሃሽ ማፕ ውስጥ ያለው ንጥረ ነገር ክስተቶች ቁጥር እንቀንሳለን
  • አዲሱን ንጥረ ነገር እንፈትሻለን
  • ቀድሞ ካለ። ወደ ክስተቱ እንጨምራለን ፡፡
  • እሱ ከሌለው ወደ ሃሽ ማፕ ውስጥ እንጨምረዋለን
  • በእያንዲንደ ድግግሞሽ ውስጥ በአይራይይሊስት ሊይ የልዩ አባላትን ብዛት እንጨምረዋሇን ወይም ማተም እንችል ይሆናል ፡፡
  • የልዩ አካላት ብዛት የሃሽማፕ መጠን ነው
ተመልከት
የሁለትዮሽ ዛፍ Leetcode መፍትሄ ከፍተኛ ጥልቀት

የሂደቱን አጠቃላይ እይታ ለመስጠት አንድ ምስል ይኸውልዎት።

እኛ እዚህ የመጠን እና የ 6 መጠን ድርድር አለን ፡፡ እንደ 3. የቀይ ድምቀቶች ተንሸራታች መስኮታችንን ስንንቀሳቀስ ንዑስ ክፍሎች ናቸው ፡፡

በመለኪያ መስኮቱ ሁሉ የተለዩ ንጥረ ነገሮችን ይቆጥሩ ኬጭንቅላታም መያያዣ መርፌ
የ 3 መጠን ለሆኑ መስኮቶች ንዑስ ክፍሎችን በማሳየት ላይ

የጃቫ ኮድ ለየት ያሉ ንጥረ ነገሮችን ለመቁጠር በእያንዳንዱ መስኮት መጠን ኬ  

// "static void main" must be defined in a public class.
public class Main 
{
    public static void countDist(int[] arr,int k)
    {
        HashMap<Integer,Integer>store=new HashMap<Integer,Integer>();
        List<Integer>ans=new ArrayList<Integer>();
        for(int i=0;i<k;i++)
        {
            if(!store.containsKey(arr[i]))
                store.put(arr[i],1);
            else
                store.put(arr[i],store.get(arr[i])+1);
        }
        ans.add(store.size());
        for(int i=k;i<arr.length;i++)
        {
            if(store.get(arr[i-k])==1)
                store.remove(arr[i-k]);
            else
                store.put(arr[i-k],store.get(arr[i-k])-1);
            if(!store.containsKey(arr[i]))
                store.put(arr[i],1);
            else
                store.put(arr[i],store.get(arr[i])+1);
            ans.add(store.size());
        }
        for(int i=0;i<ans.size();i++)
            System.out.print(ans.get(i)+" ");
    }
    public static void main(String[] args) 
    {
        int arr[] = { 1, 2, 1, 3, 4, 2, 3 }; 
        int k = 4; 
        countDist(arr, k); 
    }
}

ከጃቫ ወደ ሲ ++ እንደቀየርን ፡፡ እኛ የምንለውጠው ከ የስብስብ ማዕቀፍ ወደ STL. ይህ ማለት ከሃራይ ማፕ ፋንታ ያልተስተካከለ ካርታ እና በአርላይላይስት ምትክ ቬክተር እንጠቀማለን ማለት ነው ፡፡

አሁን ወደ C + ኮድ እንሸጋገር ፡፡

የመለኪያ ንጥረ ነገሮችን ለመቁጠር C ++ ኮድ በእያንዳንዱ መስኮት መጠን ኬ  

#include<bits/stdc++.h>
using namespace std;
void countDist(int arr[],int k,int size)
{
        unordered_map<int,int>store;
        vector<int>ans;
        for(int i=0;i<k;i++)
        {
            if(store.find(arr[i])==store.end())
                store[arr[i]]=1;
            else
                store[arr[i]]=store[arr[i]]+1;
        }
        ans.push_back(store.size());
        for(int i=k;i<size;i++)
        {
            if(store[arr[i-k]]==1)
                store.erase(arr[i-k]);
            else
                store[arr[i-k]]=store[arr[i-k]]-1;
            if(store.find(arr[i])!=store.end())
                store[arr[i]]=1;
            else
                store[arr[i]]=store[arr[i]]+1;
            ans.push_back(store.size());
        }
        for(int i=0;i<ans.size();i++)
            cout<<ans[i]<<" ";
}
int main() 
{ 
    int arr[] = { 1, 2, 1, 3, 4, 2, 3 }; 
    int size = sizeof(arr) / sizeof(arr[0]); 
    int k = 4; 
    countDist(arr, k, size); 
  
    return 0; 
}
3 4 4 3

የመለኪያ ንጥረ ነገሮችን ለመቁጠር ውስብስብነት ትንተና በእያንዳንዱ የመጠን መስኮት ኬ  

የጊዜ ውስብስብነት = ኦ (n)

የቦታ ውስብስብነት = ኦ (ኬ)

እንዴት?

ስለ ጊዜ ውስብስብነት

  • ንጥረ ነገሮችን ስንፈልግ
  • የመጀመሪያው ዙር ለ k አባሎች ይሠራል
  • ከዚያ የምንሮጠው ዑደት የመጀመሪያውን ንጥረ ነገር ይመርጣል እና ከዚያ የመጨረሻውን አካል ከግምት ውስጥ ያስገባል
  • በዚህ መንገድ ቢያንስ ቢያንስ አንድ ጊዜ ሁሉንም አካላት አነሳን
  • ይህ እንደ O (n) ጊዜን ውስብስብ ያደርገዋል
ተመልከት
አንጻራዊ ድርድር ድርድር Leetcode መፍትሔ

ስለ ጠፈር ውስብስብነት

  • የያዝነው ሃሽፕ በአንድ ጊዜ k አባሎችን ብቻ ይወስዳል
  • HashMap በመጀመሪያው ዑደት ውስጥ የመጀመሪያውን k አባሎችን ይወስዳል
  • ወደ ፊት ስንገፋ የቆዩ አባላትን አስወግደን ትኩስ አባሎችን እንጨምራለን
  • በድግግሞሽ ሁኔታ አናሳ አካላት ሊኖሩ ይችላሉ
  • ንጥረ ነገሮቹ ሁሉም የተለዩ ቢሆኑ ኬ አካላት ይኖራሉ

ማጣቀሻዎች