ترټولو اوږده فرعي سیسټم له K څخه زیات بیلابیل عناصر نلري


مشکل کچه منځني
په مکرر ډول دننه پوښتل کیږي ترلاسه کړئ Amazon د فراه تاريخي کلا دهلي فیسبوک د Microsoft سامسنګ Yandex
پیشه هاش غځېدونکې کړکۍ

ستونزه "ترټولو اوږده سابري د K مختلف عنصر نه لري" وايي چې فرض کړئ چې تاسو یو سور of ضمیمه، د ستونزې بیان د اوږدې فرعي سرې موندلو غوښتنه کوي چې د K مختلف عنصرونو څخه لوی نه وي.

بېلګهترټولو اوږده فرعي سیسټم له K څخه زیات بیلابیل عناصر نلري

arr[] = {4, 3, 5, 2, 1, 2, 0, 4, 5}
k=3
2, 1, 2, 0

تشریح

د K مختلف عناصرو سره اوږد فرعي سرې (2 ، 1 ، 2 ، 0)

arr[] = {1, 2, 3, 4}
k=2
3, 4

تشریح

د K مختلف عناصرو سره اوږد فرعي سرې (3 ، 4)

الګوریتم

  1. د هر عنصر حساب زیات کړئ او وساتئ
  2. د 0 څخه پیل کول د ځانګړو عناصرو شمیر ساتل تر هغه چې دا له k څخه لوی شي.
  3. که چیرې شمیرنه له k څخه لوی شي ، د عناصرو شمیر کمول پیل کړئ (د پیل ټکی).
  4. د شمېرنې لرې کول تر هغه وخته پورې چې موږ یو ځل بیا k ترالسه کړو مختلف عناصر هم د فرعي سرې د پیل ټکي زیاتوي.
  5. د اوږدې فرعي سرې اوږدوالي په لټه کولو سره د سرني عنصر شاخص مطابق پای تازه کړئ.
  6. د سرنی ب Printه د پای ټکو ته پیل کړئ.

تشریح

موږ دقیق صفونه ورکړی ، موږ غوښتنه کړې چې په صف کې موجود تر ټولو اوږد فرعي سرې پیدا کړو چې د K بیلابیلو عناصرو څخه زیات نه وي. موږ به ورته ورته میتود وکاروو ټوپونه. موږ باید د هر عنصر حساب زیاتولو ته دوام ورکړو ، که څه هم موږ اړتیا لرو تر ټولو اوږده فرعي سرې ومومئ. نو موږ باید د فرعي سرې د پیل ټکي او د فرعي سرې پای پای کې سترګې وساتو. نو ، موږ به هغه فرعي سرې له پیل څخه تر پایه پای ته ورسوو چې د k مختلف عنصرونو څخه ډیر نه ، چې موږ ته یې راکړئ.

موږ باید د هغه شیانو شمیر هم وساتو چې دا ډاډ ترلاسه کوي چې هیڅ شمیر باید له k څخه ډیر نه وي. راځئ چې یو مثال واخلو:

آرر [] = {4 ، 3 ، 5 ، 2 ، 1 ، 2 ، 0 ، 4 ، 5} ، k = 3

موږ د صفونو هر عنصر غوره کوو او د صفونو عنصر شمیر زیات کوو او هرځله چې موږ ګورو چې دا پیښې د لومړي ځل لپاره دي ، موږ به اوسنی شمیره لوړه کړو ، موږ به یې له k سره پرتله کړو ، موږ دا نه کوو هر څه پورې چې له K څخه لوی شي. که یوځل چې دا د K څخه لوی شي ، موږ به د 0 څخه پیل شوي عنصر شمیر راکمه کړو ، او ارزښت به زیاتوو ترڅو راتلونکي ځل موږ وکولی شو د راتلونکي عنصر شمیره راکمه کړو. موږ باید د کی left ارزښت لوړ کړو ، دا به د فرعي سرې پیل ټکي وي تر هغه چې موږ بیا k بیلابیل عناصر وموندل شي.

که موږ د صف څخه 4 ، 3 او 5 په پام کې ونیسو موږ i = 2 ، کرر = 3 لرو ، که موږ د بل عنصر لپاره لاړ شو نو موږ کرر 4 ته ترلاسه کوو موږ 2 د فرعي سرې د پیل ټکي په توګه ترلاسه کوو او موږ باید وساتو ترهغې پورې چې موږ د k مختلف عنصر ونه موندلو.

کوډ

C ++ کوډ ترڅو ترټولو اوږده subarray ومومئ چې له K څخه ډیر مشخص عنصر نلري

#include<iostream>
#include<unordered_map>
using namespace std;

void getLongestSub(int arr[], int n, int k)
{
    unordered_map<int, int> count;

    int start = 0, endp = 0, curr = 0, left = 0;
    for (int i = 0; i < n; i++)
    {
        count[arr[i]]++;
        if (count[arr[i]] == 1)
            curr++;
        while (curr > k)
        {
            count[arr[left]]--;

            if (count[arr[left]] == 0)
                curr--;

            left++;
        }
        if (i - left + 1 >= endp - start + 1)
        {
            endp = i;
            start = left;
        }
    }
    for (int i = start; i <= endp; i++)
        cout << arr[i] << " ";
}
int main()
{
    int arr[] = {4, 3, 5, 2, 1, 2, 0, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    getLongestSub(arr, n, k);
    return 0;
}
2 1 2 0

د جاوا کوډ ترڅو ترټولو اوږده فرعي ومومي ترڅو د K مختلف عنصر نه لري

import java.util.*;

class longestSubArray
{
    public static void getLongestSub(int arr[], int n, int k)
    {
        int[] count = new int[7];
        int start = 0, end = 0, curr = 0, left = 0;
        for (int i = 0; i < n; i++)
        {
            count[arr[i]]++;
            if (count[arr[i]] == 1)
                curr++;

            while (curr > k)
            {
                count[arr[left]]--;

                if (count[arr[left]] == 0)
                    curr--;
                left++;
            }
            if (i - left + 1 >= end - start + 1)
            {
                end = i;
                start = left;
            }
        }
        for (int i = start; i <= end; i++)
            System.out.print(arr[i]+" ");
    }
    public static void main(String args[])
    {
        int arr[] = {4, 3, 5, 2, 1, 2, 0, 4, 5};
        int n = arr.length;
        int k = 3;
        getLongestSub(arr, n, k);
    }
}
2 1 2 0

د پیچلتیا تحلیل

د وخت پیچلتیا

اې (N) هلته "n" په صف کې د عناصرو شمیر دی. د هش میپ کارول موږ ته اجازه درکوي چې په O (1) وخت کې دننه ، حذف ، او لټون وکړئ. پدې توګه د وخت پیچلتیا لاهم ده.

د ځای پیچلتیا

اې (N) هلته "n" په صف کې د عناصرو شمیر دی. په خورا بد حالت کې ، موږ ممکن ټول عناصر ذخیره کړو. پدې توګه د ځای پیچلتیا هم خطي ده.