Эң узун суб-массив, К-дан ашык элементтери жок  


Кыйынчылык деңгээли орто
Көп суралган Amazon Citadel Delhivery Facebook Microsoft Samsung Яндекс
согуштук тизме таштанды Жылма терезе

Сизде бар деп болжолдогон "Эң узун субарезада К-дан ашыкча элементтер жок" согуштук тизме of бүтүн, көйгөйлөрдүн ар кандай элементтеринен 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 айырмаланган элементтери бар

Algorithm  

  1. Ар бир элементтин санын көбөйтүп, сактап туруңуз
  2. 0дөн баштап, айырмаланган элементтердин санын эсептеп, ал k дан чоңураак болот.
  3. Эгерде эсептөө k ден чоң болсо, анда элементтердин санын азайта баштаңыз (баштапкы чекит).
  4. Кайра алынганга чейин эсептөөнү алып сала бериңиз k өзгөчө элементтер, ошондой эле суб-массивдин баштапкы чекитин көбөйтөт.
  5. Эң узун суб-массивдин узундугун текшерүү менен, массив элементтеринин индексине ылайык, аягын жаңыртыңыз.
  6. Массив формасын акыркы чекиттен баштап басып чыгарыңыз.

түшүндүрүү

Биз бүтүндөй сандардын массивин бердик, массивде эң узун суб-массивди аныктоону сурандык, ал k элементтерден ашпашы керек. Ушул сыяктуу ыкманы колдонууга ниеттенип жатабыз Хеширлөө. Биз ар бир элементтин санын көбөйтүшүбүз керек, бирок эң узун суб-массивди табышыбыз керек. Ошентип, биз суб-массивдин баштапкы чекитине жана суб-массивдин аяктоочу жерине көз салып турушубуз керек. Ошентип, биз ал кичи массивди башынан аягына чейин бизге берилген k өзгөчө элементтер менен басып чыгарабыз.

ошондой эле
Элементтерди жыштык боюнча иреттөө

Ошондой эле, биз эч нерсенин к-ден чоң болбошун камсыз кылган нерселердин санын санап турушубуз керек. Келгиле, бир мисал алып көрөлү:

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

Биз массивдин ар бир элементин тандап, массив элементинин санын көбөйтөбүз жана анын пайда болушу биринчи жолу болгонун текшерген сайын, учурдагы эсептөөнү көбөйтөбүз, биз аны 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" массивдеги элементтердин саны. Хэшмапты колдонуу бизге O (1) убакыттын ичинде киргизүүгө, жок кылууга жана издөөгө мүмкүнчүлүк берет. Ошентип, убакыттын татаалдыгы сызыктуу.

ошондой эле
Эки массивде тең жалпы элемент жок болуп, элементтердин минималдуу санын алып салыңыз

Космостун татаалдыгы

O (N) кайда "N" массивдеги элементтердин саны. Эң жаманы, биз бардык элементтерди сакташыбыз керек. Ошентип космостогу татаалдык дагы сызыктуу.