מערך המשנה הארוך ביותר שלא כולל יותר מ- K יסודות מובחנים


רמת קושי בינוני
נשאל לעתים קרובות אמזון בעברית מצודה מסירה פייסבוק מיקרוסופט סמסונג Yandex
מערך בליל חלון הזזה

הבעיה "מערך המשנה הארוך ביותר שאינו בעל יותר מ- K יסודות מובחנים" קובע שמניח שיש לך מערך of מספרים שלמיםהצהרת הבעיה מבקשת לברר את מערך המשנה הארוך ביותר שיש בו לא יותר מ- k יסודות שונים.

דוגמהמערך המשנה הארוך ביותר שלא כולל יותר מ- K יסודות מובחנים

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

הסבר

מערך המשנה הארוך ביותר (2, 1, 2, 0) עם k אלמנטים מובחנים

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

הסבר

מערך המשנה הארוך ביותר (3, 4) עם אלמנטים מובחנים k

אַלגוֹרִיתְם

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

הסבר

נתנו מערך של מספרים שלמים, ביקשנו לגלות את מערך המשנה הארוך ביותר הקיים במערך שיש בו לא יותר מ- k יסודות נפרדים. אנו הולכים להשתמש בשיטה דומה לזו has has. עלינו להמשיך ולהגדיל את ספירת כל אלמנט, אם כי עלינו למצוא את מערך המשנה הארוך ביותר. לכן עלינו לפקוח עין על נקודת ההתחלה של מערך המשנה ובנקודת הסיום של מערך המשנה. לכן, אנו נדפיס מערך משנה זה מההתחלה ועד הסוף עם לא יותר מ- k יסודות נפרדים, שניתנו לנו.

עלינו גם לשמור על ספירת הדבר הזה שמוודא שאף מספר לא יעלה על יותר מ- k. הבה ניקח דוגמא:

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

אנו בוחרים כל אלמנט במערך ומגדילים את ספירת אלמנט המערך ובכל פעם שנבדוק אם התרחשותו בפעם הראשונה, נגדיל את הספירה הנוכחית, אנו הולכים להשוות אותה עם k, אנחנו לא עושים כל דבר עד שהוא נהיה גדול מ- k. אם ברגע שהוא נהיה גדול מ- k, נפחית את ספירת האלמנט החל מ- 0, ונגרום את הגדלת הערך כך שבפעם הבאה נוכל להקטין את ספירת האלמנט הבא. עלינו להגדיל את הערך של שמאל, זו תהיה נקודת המוצא של מערך המשנה עד שנמצא שוב k אלמנטים נפרדים.

אם ניקח בחשבון 4, 3 ו- 5 ממערך יש לנו i = 2, curr = 3, אם נלך לאלמנט הבא נקבל את curr כ -4 נקבל את 2 כנקודת ההתחלה של תת מערך ועלינו לשמור הולך עד שמצאנו את האלמנטים המובהקים יותר מ- k.

קופונים

קוד C ++ לאיתור מערך המשנה הארוך ביותר שאינו כולל יותר מ- 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

קוד Java לאיתור מערך המשנה הארוך ביותר שלא כולל יותר מ- 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

ניתוח מורכבות

מורכבות זמן

O (n) איפה "N" הוא מספר האלמנטים במערך. שימוש ב- hashmap מאפשר לנו להוסיף, למחוק ולחפש בזמן O (1). לפיכך מורכבות הזמן היא לינארית.

מורכבות בחלל

O (n) איפה "N" הוא מספר האלמנטים במערך. במקרה הגרוע ביותר, ייתכן שנצטרך לאחסן את כל האלמנטים. לפיכך מורכבות החלל היא גם לינארית.