К өлчөмүнүн ар бир терезесинде өзүнчө элементтерди санап чыгыңыз


Кыйынчылык деңгээли орто
Көп суралган Accolite Amazon 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 циклин иштетүү керек
  • HashMap менен бардык элементтердин санын санап туруңуз
  • Ачкыч - бул элементтин HashMap ичинде канча жолу пайда болгонуна ээ болгон элемент
  • Алга бара жатканда, биз HashMap ичинен биринчи элементти алып салабыз
  • Эгерде элемент бир эле жолу пайда болсо, биз аны жөн эле алып салабыз
  • Башка жол менен биз HashMap ичиндеги элементтин пайда болушун азайтабыз
  • Жаңы элементти текшеребиз
  • Эгерде ал алдын ала бар болсо. Биз анын пайда болушуна кошобуз.
  • Эгер ал жок болсо, биз аны HashMap картасына кошобуз
  • Ар бир кайталоодо ArrayListке уникалдуу элементтердин санын кошобуз, болбосо аны басып чыгарышыбыз мүмкүн.
  • Уникалдуу элементтердин саны - HashMap өлчөмү

Бул жерде процесстин жалпы баяндамасын берүү үчүн сүрөт бар.

Бизде көлөмү 6 масштабы бар жана k катары берилген 3. Кызыл түстөгү көз ирмемдер биздин жылдырылган терезебизди жылдырганда топтомдор.

К өлчөмүнүн ар бир терезесинде өзүнчө элементтерди санап чыгыңыз
3-өлчөмдөгү терезе үчүн ички топтомдор көрсөтүлүүдө

Өлчөмдүн ар бир терезесиндеги айырмаланган элементтерди эсептөө үчүн Java коду

// "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); 
    }
}

Javaдан C ++ которулганда. Биз өзгөрөбүз Коллекциянын алкагы STLге. Демек, биз HashMap ордуна иретке салынбаган картаны жана ArrayListтин ордуна векторду колдонобуз.

Эми 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

Өлчөмдүн ар бир терезесинде санактын айырмаланган элементтери үчүн татаалдыкты талдоо

Убакыт татаалдыгы = O (n)

Космостун татаалдыгы = O (k)

Кандай?

Убакыттын татаалдыгы жөнүндө

  • Биз элементтерин издеп жатканда
  • Биринчи цикл k элементтери үчүн иштейт
  • Андан кийин биз иштеткен цикл биринчи элементти тандап, андан соң акыркы элементти эске алат
  • Ошентип, биз бардык элементтерди жок дегенде бир жолу тандап алдык
  • Бул убакытты татаалдаштырат O (n)

Космостун татаалдыгы жөнүндө

  • Биздеги HashMap бир эле учурда k элементин гана алат
  • HashMap биринчи циклдеги биринчи k элементтерин алат
  • Биз алга жылганда эски элементтерден арылып, жаңы элементтерди кошобуз
  • Кайталанган учурда, азыраак элементтер болушу мүмкүн
  • элементтери ар башка болгон учурда k элементтер болот

шилтемелер