വലുപ്പത്തിന്റെ ഓരോ വിൻ‌ഡോയിലും വ്യത്യസ്‌ത ഘടകങ്ങൾ‌ എണ്ണുക  


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു അക്കോലൈറ്റ് ആമസോൺ മൈക്രോസോഫ്റ്റ്
അറേ ഹാഷ് സ്ലൈഡിംഗ് വിൻഡോ

കുറച്ചു കാലമായി ഞങ്ങൾ കൈകാര്യം ചെയ്യുന്ന ഒന്നാണ് ഉപസെറ്റുകൾ. അവസാന എപ്പിസോഡിൽ, വ്യത്യസ്തമായ ഇരട്ട സംഖ്യകൾ ഉപയോഗിച്ച് ഞങ്ങൾക്ക് നിർമ്മിക്കാൻ കഴിയുന്ന ഉപസെറ്റുകളുടെ എണ്ണം ഞങ്ങൾ ഉൾപ്പെടുത്തി. കെ വലുപ്പമുള്ള ഓരോ വിൻഡോയിലും ഇത്തവണ വ്യത്യസ്ത ഘടകങ്ങൾ കണക്കാക്കുന്നു.

വകുപ്പ് -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 ന്റെ ഒരു ലൂപ്പ് പ്രവർത്തിപ്പിക്കുക
  • ഒരു ഹാഷ്‌മാപ്പ് ഉപയോഗിച്ച് എല്ലാ ഘടകങ്ങളുടെയും എണ്ണം നിലനിർത്തുക
  • ഹാഷ്മാപ്പിൽ മൂലകം എത്ര തവണ സംഭവിക്കുന്നു എന്നതിന്റെ മൂല്യമുള്ള മൂലകമാണ് കീ
  • ഞങ്ങൾ മുന്നോട്ട് പോകുമ്പോൾ ഹാഷ്‌മാപ്പിൽ നിന്ന് ആദ്യ ഘടകം നീക്കംചെയ്യുന്നു
  • മൂലകം ഒരിക്കൽ സംഭവിച്ചാൽ ഞങ്ങൾ അത് നീക്കംചെയ്യും
  • അല്ലാത്തപക്ഷം, ഹാഷ്‌മാപ്പിലെ മൂലകത്തിന്റെ സംഭവങ്ങളുടെ എണ്ണം ഞങ്ങൾ കുറയ്‌ക്കുന്നു
  • ഞങ്ങൾ പുതിയ ഘടകം പരിശോധിക്കുന്നു
  • അത് മുമ്പേ നിലവിലുണ്ടെങ്കിൽ. അതിന്റെ സംഭവത്തിലേക്ക് ഞങ്ങൾ ചേർക്കുന്നു.
  • അത് നിലവിലില്ലെങ്കിൽ ഞങ്ങൾ അത് ഹാഷ്‌മാപ്പിലേക്ക് ചേർക്കുന്നു
  • ഓരോ ആവർത്തനത്തിലും, ഞങ്ങൾ അറേലിസ്റ്റിലേക്ക് അദ്വിതീയ ഘടകങ്ങളുടെ എണ്ണം ചേർക്കുന്നു അല്ലെങ്കിൽ ഞങ്ങൾ അത് പ്രിന്റുചെയ്യാം.
  • അദ്വിതീയ ഘടകങ്ങളുടെ എണ്ണം ഹാഷ്‌മാപ്പിന്റെ വലുപ്പമാണ്
ഇതും കാണുക
ബൈനറി ട്രീ ലീറ്റ്കോഡ് പരിഹാരത്തിന്റെ പരമാവധി ആഴം

പ്രക്രിയയുടെ ഒരു അവലോകനം നൽകുന്നതിന് ഇവിടെ ഒരു ചിത്രം ഉണ്ട്.

ഞങ്ങൾക്ക് ഇവിടെ 6 വലുപ്പമുള്ള ഒരു ശ്രേണി ഉണ്ട്, k 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 ++ നായുള്ള കോഡിലേക്ക് മാറാം.

വലുപ്പത്തിന്റെ ഓരോ വിൻ‌ഡോയിലും വ്യത്യസ്‌ത ഘടകങ്ങൾ‌ക്കായുള്ള സി ++ കോഡ്  

#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

വലുപ്പത്തിന്റെ ഓരോ വിൻ‌ഡോയിലും വ്യത്യസ്ത ഘടകങ്ങളുടെ എണ്ണത്തിനായുള്ള സങ്കീർണ്ണത വിശകലനം  

സമയ സങ്കീർണ്ണത = O (n)

ബഹിരാകാശ സങ്കീർണ്ണത = O (k)

എങ്ങനെ?

സമയ സങ്കീർണ്ണതയെക്കുറിച്ച്

  • ഞങ്ങൾ ഘടകങ്ങൾ തിരയുമ്പോൾ
  • ആദ്യത്തെ ലൂപ്പ് k ഘടകങ്ങൾക്കായി പ്രവർത്തിക്കുന്നു
  • ഞങ്ങൾ പ്രവർത്തിപ്പിക്കുന്ന ലൂപ്പ് ആദ്യ ഘടകം തിരഞ്ഞെടുത്ത് അവസാന ഘടകം കണക്കിലെടുക്കുന്നു
  • ഈ രീതിയിൽ, ഞങ്ങൾ എല്ലാ ഘടകങ്ങളും ഒരു തവണയെങ്കിലും തിരഞ്ഞെടുത്തു
  • ഇത് സമയ സങ്കീർണ്ണതയെ O (n) ആയി മാറ്റുന്നു
ഇതും കാണുക
ആപേക്ഷിക അടുക്കൽ അറേ ലീറ്റ്കോഡ് പരിഹാരം

ബഹിരാകാശ സങ്കീർണ്ണതയെക്കുറിച്ച്

  • ഞങ്ങളുടെ കൈവശമുള്ള ഹാഷ്‌മാപ്പ് ഒരു സമയം k ഘടകങ്ങൾ മാത്രമേ എടുക്കൂ
  • ആദ്യ ലൂപ്പിലെ ആദ്യത്തെ k ഘടകങ്ങൾ ഹാഷ്‌മാപ്പ് എടുക്കുന്നു
  • നമ്മൾ മുന്നോട്ട് പോകുമ്പോൾ പഴകിയ മൂലകങ്ങളിൽ നിന്ന് മുക്തി നേടുകയും പുതിയ ഘടകങ്ങൾ ചേർക്കുകയും ചെയ്യുന്നു
  • ആവർത്തനത്തിന്റെ കാര്യത്തിൽ, കുറഞ്ഞ ഘടകങ്ങൾ ഉണ്ടാകാം
  • മൂലകങ്ങളെല്ലാം വ്യത്യസ്തമാണെങ്കിൽ k ഘടകങ്ങൾ ഉണ്ടാകും

അവലംബം