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.
Mündəricat
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 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
