عناصر مشخص را در هر پنجره با اندازه K بشمارید


سطح دشواری متوسط
اغلب در همبستگی آمازون مایکروسافت
صف مخلوط پنجره کشویی

زیرمجموعه ها مواردی است که ما مدتی است با آنها دست و پنجه نرم می کنیم. در قسمت آخر ، ما تعداد زیرمجموعه هایی را که می توانیم ایجاد کنیم با اعداد زوج مجزا پوشش دادیم. این بار عناصر مشخص را در هر پنجره با اندازه K می شماریم.

بخش 1

در مورد مشکل

با توجه به یک آرایه مرتب نشده از اعداد صحیح. ما باید تعداد متمایز عدد صحیح هر زیر مجموعه را دریابیم. بیایید بیانیه را با یک نمونه آزمایشی بررسی کنیم.

داده شده:

آرایه: {1,2,3,4,4,2,3،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX}

اندازه زیر مجموعه ها: 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 داده شده است. برجسته های قرمز هنگام حرکت پنجره کشویی ، زیر مجموعه هستند.

عناصر مشخص را در هر پنجره با اندازه K بشمارید
نمایش زیرمجموعه های پنجره به اندازه 3

کد جاوا برای شمارش عناصر مشخص در هر پنجره با اندازه K

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

همانطور که از جاوا به ++ C تغییر می دهیم. ما از چارچوب مجموعه به STL. این بدان معناست که ما به جای HashMap از نقشه غیر مرتب و به جای ArrayList از بردار استفاده خواهیم کرد.

اکنون اجازه دهید به کد C ++ برویم.

C ++ کد برای شمارش عناصر مشخص در هر پنجره با اندازه K

#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

پیچیدگی زمان = O (n)

پیچیدگی فضا = O (k)

چگونه؟

درباره پیچیدگی زمان

  • وقتی عناصر را جستجو می کنیم
  • اولین حلقه برای عناصر k اجرا می شود
  • حلقه ای که ما اجرا می کنیم اولین عنصر را انتخاب می کند و سپس آخرین عنصر را در نظر می گیرد
  • به این ترتیب ، حداقل یک بار همه عناصر را برداشته ایم
  • این باعث می شود پیچیدگی زمان به صورت O (n) باشد

درباره پیچیدگی فضا

  • HashMap که ما داریم هربار فقط k عنصر می گیرد
  • HashMap اولین عناصر k را در حلقه اول می گیرد
  • همانطور که به جلو می رویم ، از عناصر بیات خلاص می شویم و عناصر تازه اضافه می کنیم
  • در صورت تکرار ، ممکن است عناصر کمتری وجود داشته باشد
  • در صورت متمایز بودن عناصر ، k عنصر وجود خواهد داشت

منابع