לאָנגעסט סובאַרראַי מיט מער ווי ק בוילעט עלעמענטן  


שוועריקייט לעוועל מיטל
אָפט געבעטן אין אַמאַזאָן ציטאַדעל דעליווערי facebook מייקראָסאָפֿט סאַמסונג יאַנדעקס
מענגע האַש סליידינג ווינדאָו

די פּראָבלעם "לאָנגעסט סובאַרראַי האט נישט מער ווי ק בוילעט עלעמענטן" שטאַטן אַז רעכן איר האָבן אַן מענגע of ינטאַדזשערז, די פּראָבלעם ויסזאָגונג פרעגט צו געפֿינען די לאָנגעסט סאַב-מענגע וואָס האט ניט מער ווי ק פאַרשידענע עלעמענטן.

בייַשפּיללאָנגעסט סובאַרראַי מיט מער ווי ק בוילעט עלעמענטןשפּילקע  

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

דערקלערונג

לאָנגעסט סאַב-מענגע (2, 1, 2, 0) מיט ק בוילעט עלעמענטן

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

דערקלערונג

לאָנגעסט סאַב-מענגע (3, 4) מיט ק בוילעט עלעמענטן

אַלגאָריטהם  

  1. פאַרגרעסערן און האַלטן די ציילן פון יעדער עלעמענט
  2. סטאַרטינג פון 0 האַלטן אַ ציילן פון בוילעט עלעמענטן ביז עס ווערט גרעסער ווי ק.
  3. אויב דער ציילן ווערט גרעסער ווי ק, אָנהייבן דיקריסט די ציילן פון עלעמענטן (סטאַרטינג פונט).
  4. האַלטן רימוווינג די ציילן ביז מיר באַקומען ווידער ק פאַרשידענע עלעמענטן אויך פאַרגרעסערן די סטאַרטינג פונט פון סאַב-מענגע.
  5. דערהייַנטיקן די סוף לויט די מענגע עלעמענט אינדעקס דורך קאָנטראָלירונג די לאָנגעסט סאַב-מענגע לענג.
  6. דרוק דעם מענגע פאָרעם סטאַרטינג צו די סוף-פונט.

דערקלערונג

מיר האָבן געגעבן אַ מענגע פון ​​ינטאַדזשערז, מיר האָבן געבעטן צו געפֿינען אויס די לאָנגעסט סאַב-מענגע אין אַ מענגע וואָס האט נישט מער ווי ק בוילעט עלעמענטן. מיר וועלן נוצן אַ ענלעך אופֿן ווי כאַשינג. מיר מוזן האַלטן ינקריסינג די ציילן פון יעדער עלעמענט, כאָטש מיר דאַרפֿן צו געפֿינען די לאָנגעסט סאַב-מענגע. מיר מוזן האַלטן אַן אויג אויף די סטאַרטינג פונט פון די סאַב-מענגע און אין די סאָף פונט פון די סאַב-מענגע. אַזוי, מיר וועלן דרוקן דעם סאַב-מענגע פֿון אָנהייב צו סוף מיט נישט מער ווי ק בוילעט עלעמענטן.

זע אויך
סאָרט עלעמענטן לויט אָפטקייַט

מיר אויך האָבן צו האַלטן די ציילן פון די זאַך וואָס מאכט זיכער אַז קיין נומער זאָל יקסיד גרעסער ווי ק. לאָמיר נעמען אַ ביישפּיל:

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

מיר קלייַבן יעדער עלעמענט פון דער מענגע און פאַרגרעסערן די ציילן פון אַ מענגע עלעמענט, און יעדער מאָל ווען מיר קאָנטראָלירן אויב די פּאַסירונג איז פֿאַר די ערשטער מאָל, מיר וועלן פאַרגרעסערן די איצטיקע ציילן, מיר וועלן פאַרגלייכן עס מיט ק. עפּעס ביז עס ווערט גרעסער ווי ק. אויב אַמאָל עס ווערט גרעסער ווי ק, מיר וועלן פאַרקלענערן די ציילן פון עלעמענט סטאַרטינג פון 0, און מאַכן פאַרגרעסערן די ווערט אַזוי אַז ווייַטער מאָל מיר קענען פאַרמינערן די ציילן פון דער ווייַטער עלעמענט. מיר זאָל פאַרגרעסערן די ווערט פון לינקס, דאָס וועט זיין די סטאַרטינג פונט פון סאַב-מענגע ביז מיר געפונען ק פאַרשידענע עלעמענטן.

אויב מיר באַטראַכטן 4, 3 און 5 פֿון אַ מענגע מיר האָבן i = 2, curr = 3, אויב מיר גיין פֿאַר די ווייַטער עלעמענט, מיר באַקומען די curr ווי 4 מיר באַקומען די 2 ווי די סטאַרטינג פונט פון סאַב-מענגע און מיר זאָל האַלטן ביז מיר געפונען די מער ווי ק בוילעט עלעמענטן.

קאָדעקס  

C ++ קאָד צו געפֿינען לאָנגעסט סובאַרראַי וואָס האט ניט מער ווי ק בוילעט עלעמענטן

#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

ז'אבא קאָד צו געפֿינען לאָנגעסט סובאַרראַי מיט מער ווי ק בוילעט עלעמענטן

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” איז די נומער פון עלעמענטן אין די מענגע. ניצן אַ האַשמאַפּ אַלאַוז אונדז צו אַרייַן, ויסמעקן און זוכן אין אָ (1) צייט. אזוי די צייט קאַמפּלעקסיטי איז לינעאַר.

זע אויך
אַראָפּנעמען די מינימום נומער פון עלעמענטן אַזאַ ווי קיין פּראָסט עלעמענט איז ביי ביידע עריי

ספעיס קאַמפּלעקסיטי

אָ (N) ווו “N” איז די נומער פון עלעמענטן אין די מענגע. אין די ערגסט פאַל, מיר קען האָבן צו קראָם אַלע עלעמענטן. אזוי די פּלאַץ קאַמפּלעקסיטי איז אויך לינעאַר.