Найдовший підмасив, що не має більше ніж K різних елементів  


Рівень складності Medium
Часто запитують у Амазонка Цитадель Делівері Facebook Microsoft Samsung Яндекс
масив Мішанина Розсувне вікно

Проблема "Найдовший підмасив, що не має більше ніж K різних елементів", говорить про те, що у вас є масив of цілих чисел, постановка задачі вимагає виявити найдовший підмасив, який має не більше k різних елементів.

ПрикладНайдовший підмасив, що не має більше ніж K різних елементівPin  

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 різних елементів. Ми будемо використовувати подібний метод, як хешування. Ми повинні продовжувати збільшувати кількість кожного елемента, хоча нам потрібно знайти найдовший підмасив. Отже, ми повинні стежити за початковою точкою підмасиву та кінцевою точкою підмасиву. Отже, ми надрукуємо цей підмасив від початку до кінця з не більше k окремими елементами, наданими нам.

Дивись також
Сортувати елементи за частотою

Ми також повинні вести підрахунок тієї речі, яка гарантує, що жодне число не повинно перевищувати k. Візьмемо приклад:

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

Ми вибираємо кожен елемент масиву і збільшуємо кількість елементів масиву, і кожного разу, коли перевіряємо, чи воно трапляється вперше, ми збільшуємо поточний рахунок, збираємося порівняти його з k, ми цього не робимо що-небудь, поки воно не стане більше k. якщо коли він стане більшим за k, ми зменшимо кількість елементів, починаючи з 0, і зробимо збільшення значення, щоб наступного разу ми могли зменшити кількість наступного елемента. Ми повинні збільшити значення left, це буде початковою точкою підмасиву, поки ми знову не знайдемо k різних елементів.

Якщо ми розглянемо 4, 3 і 5 з масиву, у нас буде i = 2, curr = 3, якщо ми перейдемо до наступного елемента, ми отримаємо curr як 4, то отримаємо 2 як початкову точку підмасиву, і нам слід тримати до тих пір, поки ми не знайдемо більше ніж k різних елементів.

код  

Код С ++ для пошуку найдовшого підмасиву, що не має більше ніж 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

Аналіз складності  

Складність часу

О (п) де "N" - кількість елементів у масиві. Використання хеш-карти дозволяє нам вставляти, видаляти та шукати за час O (1). Таким чином, часова складність є лінійною.

Дивись також
Видаліть таку мінімальну кількість елементів, щоб не було спільного елемента в обох масивах

Складність простору

О (п) де "N" - кількість елементів у масиві. У гіршому випадку нам, можливо, доведеться зберігати всі елементи. Таким чином, складність простору також є лінійною.