Најдужи подред који нема више од К различитих елемената  


Ниво тешкоће Средњи
Често питани у амазонка Цитадела Делхивери фацебоок мицрософт самсунг иандек
Ред Хасх Клизни прозор

Проблем „Најдужа подреза која нема више од К различитих елемената“ наводи да претпостављамо да имате поредак 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. Одштампајте образац низа почев од крајње тачке.

Објашњење

Дали смо низ целих бројева, тражили смо да сазнамо најдужи под-низ присутан у низу који има не више од к различитих елемената. Користићемо сличан метод као хасхинг. Морамо да наставимо да повећавамо број сваког елемента, иако морамо да пронађемо најдужи под-низ. Дакле, морамо пазити на почетну тачку под-низа и на завршну тачку под-низа. Дакле, тај подниз ћемо исписати од почетка до краја са не више од к различитих елемената који су нам дати.

Види такође
Поредај елементе по учесталости

Такође морамо одржавати бројање те ствари која осигурава да ниједан број не прелази већи од к. Узмимо пример:

Арр [] = {4, 3, 5, 2, 1, 2, 0, 4, 5}, к = 3

Одабиремо сваки елемент низа и повећавамо број елемента низа и сваки пут када проверимо да ли је његово појављивање први пут, повећаћемо тренутно бројање, упоредићемо га са к, не радимо било шта док не постане веће од к. ако једном постане веће од к, смањићемо број елемената почев од 0 и повећаћемо вредност тако да следећи пут можемо смањити број следећег елемента. Требали бисмо повећати вредност лефт, то ће бити почетна тачка под-низа док поново не пронађемо к различитих елемената.

Ако узмемо у обзир 4, 3 и 5 из низа имамо и = 2, цурр = 3, ако кренемо за следећим елементом, добићемо цурр као 4, добијамо 2 као почетну тачку под-низа и требало би да задржимо док нисмо пронашли више од к различитих елемената.

код  

Ц ++ код за проналажење најдужег низа који нема више од К различитих елемената

#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

Анализа сложености  

Сложеност времена

Он) где „Н“ је број елемената у низу. Коришћење хасхмапе омогућава нам уметање, брисање и претрагу за О (1) време. Стога је временска сложеност линеарна.

Види такође
Уклоните минималан број елемената таквих да у оба поља не постоји заједнички елемент

Сложеност простора

Он) где „Н“ је број елемената у низу. У најгорем случају, можда ћемо морати да ускладиштимо све елементе. Стога је сложеност простора такође линеарна.