К хэмжээтэй цонх бүрт ялгаатай элементүүдийг тоол


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Accolite Амазоны Microsoft-
Array Хаш Гулгадаг цонх

Дэд бүлгүүд бол бидний харьцаж байсан зүйл юм. Сүүлийн цувралд бид олон дэд бүлгүүдийн тоог тэгш тэгш тоогоор оруулсан болно. Энэ удаад бид К хэмжээтэй цонх бүрт ялгаатай элементүүдийг тоолж байна.

Хэсэг-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 хэмжээтэй цонхны дэд хэсгүүдийг харуулж байна

K хэмжээтэй цонх бүрт ялгаатай элементүүдийг тоолох 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 элемент байх болно

Ашигласан материал