K ölçülü hər pəncərədə fərqli elementləri sayın

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Akkolit Amazon microsoft
Geyim Sükut Sürüşmə pəncərəBaxılıb 26

Alt dəstlər bir müddətdir məşğul olduğumuz bir şeydir. Son bölümdə edə bildiyimiz alt dəstlərin sayını fərqli cüt ədədlərlə əhatə etdik. Bu dəfə hər K ölçülü pəncərədə fərqli elementləri sayırıq.

Bölmə-1

Problem haqqında.

Sıralanmamış bir tam sıra verilir. Hər alt çoxluğun fərqli sayını tapmaq lazımdır. Nümunə sınaq işi ilə ifadəni nəzərdən keçirək.

Verilmişdir:

Dizi: {1,2,3,4,4,2,3}

Alt dəstlərin ölçüsü: 4

Mümkün alt qruplar ola bilər:

1,2,3,4 {}

2,3,4,4 {}

3,4,4,2 {}

4,4,2,3 {}

Yuxarıdakı alt qrupların hər birindəki unikal nömrələr bunlardır:

4,3,2 və 3

Bölmə-2

Problemə yanaşmağımızın bir çox yolu var. Ancaq qalanları arasında ən yaxşısını müzakirə edəcəyəm. Alt qrupları genişləndirəndə izləyicilərim bir nümunə görərdilər. Hər pəncərə üçün k ölçüsünü qorumaq üçün təzə bir element əlavə etdiyimiz üçün ilk elementi son pəncərədən buraxdıq.

Prosesi bir-bir nəzərdən keçirək

  • Birincisi, ilk pəncərənin bütün elementlərindən təkrarlamaq üçün bir k döngəsini işə salın
  • HashMap ilə bütün elementlərin sayını qoruyun
  • Açar, elementin HashMap-də baş vermə sayı olan dəyəri olan elementdir
  • İrəli getdikcə ilk elementi HashMap-dən çıxarırıq
  • Element yalnız bir dəfə baş verərsə, sadəcə onu çıxarırıq
  • Əks təqdirdə HashMap-də elementin meydana gəlmə sayını azaldırıq
  • Təzə elementi yoxlayırıq
  • Əvvəlcədən varsa. Onun meydana gəlməsini əlavə edirik.
  • Əgər mövcud deyilsə, onu HashMap-ə əlavə edirik
  • Hər təkrarlamada, unikal elementlərin sayını ArrayList-ə əlavə edirik və ya çap edə bilərik.
  • Unikal elementlərin sayı HashMap ölçüsüdür

Budur prosesə ümumi baxış vermək üçün bir şəkil.

Burada 6 ölçülü bir sıra var və k 3 olaraq verildi. Sürüşən pəncərəmizi hərəkət etdirdikdə qırmızı məqamlar alt hissələrdir.

K ölçülü hər pəncərədə fərqli elementləri sayınPin
3 ölçülü pəncərə üçün alt dəstlər göstərilir

K ölçülü hər pəncərədə fərqli elementləri saymaq üçün Java kodu

// "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-dan C ++ dilinə keçdiyimiz zaman. Bizdən dəyişirik Kolleksiya çərçivəsi STL-yə. Bu, HashMap əvəzinə sıralanmamış bir xəritə və ArrayList əvəzinə vektordan istifadə edəcəyimiz deməkdir.

İndi C ++ koduna keçək.

K ölçüsünün hər pəncərəsində fərqli elementlərin sayılması üçün C ++ kodu

#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

K Ölçünün Hər Pəncərəsindəki Fərqli Elementlər üçün Mürəkkəblik Analizi

Zaman Mürəkkəbliyi = O (n)

Kosmik Mürəkkəblik = O (k)

Necə?

Zamanın mürəkkəbliyi haqqında

  • Elementləri axtardığımızda
  • İlk döngə k elementləri üçün işləyir
  • Daha sonra çalışdığımız döngə ilk elementi seçir və sonra son elementi nəzərə alır
  • Bu şəkildə ən azı bir dəfə bütün elementləri götürmüşük
  • Bu, O (n) kimi zamanın mürəkkəbliyini təmin edir.

Kosmik Mürəkkəblik haqqında

  • Əldə etdiyimiz HashMap hər dəfə yalnız k element götürür
  • HashMap ilk döngədə ilk k elementləri götürür
  • İrəlilədikcə köhnəlmiş elementlərdən qurtulur və təzə elementlər əlavə edirik
  • Təkrarlama halında daha az element ola bilər
  • elementlərin hamısı bir-birindən fərqli olduqda k elementləri olacaqdır

References

Translate »