Най-малкият подмасив с k Различни числа  


Ниво на трудност Трудно
Често задавани в Амазонка Google
Array Хашиш Плъзгащ се прозорец Двупосочен

Да предположим, че имате цяло число масив и число k. Изложението на проблема изисква да се открие най-малкият подмасив от обхват (l, r) включително, по такъв начин, че в този най-малък подмасив присъстват точно k различни числа.

Пример  

Вход:

{1, 2, 2, 3, 4, 5, 5}

k = 3

Изход:

2, 4

Обяснение:

{2, 3, 4} е най-малкият подмасив, започващ от 2nd индекс до 4th индекс с k, т.е. 3 различни елемента.

Вход:

{2, 5, 6, 7}

k = 2

Изход:

2, 3

Обяснение:

{2, 5} е най-малкият под-масив, започващ от 2-ри индекс до 3-ти индекс с k, т.е. 2 отделни елемента.

алгоритъм  

  1. Задайте отделния елемент на 0, а лявата и дясната указатели на -1.
  2. Преминаване през масива,
  3. Увеличаване на дясната страна с 1, ако нито един от отделните елементи не е по-малък от даденото число k,
  4. След това увеличете броя и съхранете честотата на елемента на масива в карта.
  5. Ако отделни елементи са равни на даденото число k и така образуваната дължина е по-малка от актуализираната по-рано дължина, тогава ляв и десен странични указатели и прекъсване.
  6. Ако се установи, че броят на отделните елементи е по-малък от k, прекъснете.
  7. Проверете дали броят на отделните елементи е равен на k, след това увеличете указателите отдясно.
  8. Ако отделни елементи са равни на даденото число k и така образуваната дължина е по-малка от актуализираната по-рано дължина, тогава ляв и десен странични указатели и прекъсване.
  9. Проверете дали честотата на елемента е 1, след това премахнете този елемент от картата, в противен случай намалете броя на честотата на този елемент
  10. Ако се установи, че показалецът на лявата страна е 0, а дясната страна е равна на n, това означава, че е невалиден.
  11. В противен случай отпечатайте стойностите отляво и отдясно.
Вижте също
Относително сортиране на масив Leetcode решение

Обяснение  

Съхранявайте честотата на всеки елемент на масива, докато обхождате масива, и изберете всеки елемент на масив и проверете дали размерът на картата е по-малък от k, ако се установи, че е по-малък от k, отколкото трябва да преброим и съхраним честотата на този елемент на масива и дали размерът на картата намира k (различен номер на елемент), а също така текущата дължина е по-малка от предишната дължина на под-масива, тогава ще актуализираме указателите отляво и отдясно. Всичко това ще върти в цикъл, докато цялата карта не бъде обходена веднъж.

Ако размерът на картата се окаже по-малък от k, тогава прекъснете. Имаме стойностите на карта. Цикълът ще продължи, докато размерът на картата се окаже равен на k, установи се, че честотата на масивния елемент в картата е равна на 1, тогава трябва да премахнем този конкретен елемент от картата, в противен случай трябва да намалим честота на този конкретен елемент от карта. Отново ще проверим дали размерът на картата е равен на k и дължината на текущия подмасив е по-малка от предварително актуализираната дължина, след това актуализирайте указателите отляво и отдясно. Ако честотата на елемента на масива е 1, премахнете този елемент, иначе намалете честотата на елемента.

След обхождането на масива, ако се установи, че левият страничен указател е 0, а десният - n, това означава, че е невалиден k. В противен случай се отпечатва стойността на левия и десния страничен указател, която би била начална и крайна точка на най-малкия подмасив включително.

Вижте също
Валидно судоку

изпълнение  

Програмата на C ++ за най-малкия подмасив с k Различни числа # включва

#include<map>

using namespace std;

void getSmallestSubarray(int arr[], int n, int k)
{
    int left = 0, right = n;
    int j = -1;
    map<int, int> MAP;
    for (int i=0; i<n; i++)
    {
        while (j < n)
        {
            j++;
            if (MAP.size() < k)
                MAP[arr[j]]++;

            if (MAP.size() == k && ((right - left) >= (j - i)))
            {
                left = i;
                right = j;
                break;
            }

        }
        if (MAP.size() < k)
            break;

        while (MAP.size() == k)
        {
            if (MAP[arr[i]] == 1)
                MAP.erase(arr[i]);
            else
                MAP[arr[i]]--;

            i++;

            if (MAP.size() == k && (right - left) >= (j - i))
            {
                left = i;
                right = j;
            }
        }
        if (MAP[arr[i]] == 1)
            MAP.erase(arr[i]);
        else
            MAP[arr[i]]--;
    }
    if (left == 0 && right == n)
        cout << "Invalid k" << endl;
    else
        cout << left << " " << right;
}
int main()
{
    int arr[] = {1, 2, 2, 3, 4, 5, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    getSmallestSubarray(arr, n, k);
    return 0;
}
2 4

Програма Java за най-малкия подмасив с k разграничени числа

import java.util.HashMap;
import java.util.Map;
class smallestSubArray
{
    public static void getSmallestSubarray(int arr[], int n, int k)
    {
        int left = 0, right = n;
        int j = -1;
        HashMap<Integer, Integer> MAP=new HashMap<>();
        for (int i=0; i<n; i++)
        {
            while (j < n-1)
            {
                j++;
                if (MAP.size() < k)
                {

                    if(MAP.containsKey( arr[j] ))
                        MAP.put( arr[j], MAP.get( arr[j] ) + 1 );
                    else
                        MAP.put(arr[j],1);
                }

                if (MAP.size() == k && ((right - left) >= (j - i)))
                {
                    left = i;
                    right = j;
                    break;
                }
            }
            if (MAP.size() < k)
                break;

            while (MAP.size() == k)
            {
                if (MAP.get(arr[i]) == 1)
                    MAP.remove(arr[i]);
                else
                    MAP.put(arr[i], MAP.get(arr[i])-1);

                i++;

                if (MAP.size() == k && (right - left) >= (j - i))
                {
                    left = i;
                    right = j;
                }
            }
            if (MAP.get(arr[i]) == 1)
                MAP.remove(arr[i]);
            else
                MAP.put(arr[i], MAP.get(arr[i])-1);
        }
        if (left == 0 && right == n)
            System.out.println("Invalid k");
        else
            System.out.println(left+" "+right);
    }
    public static void main(String [] args)
    {
        int arr[] = {1, 2, 2, 3, 4, 5, 5};
        int n = arr.length;
        int k = 3;
        getSmallestSubarray(arr, n, k);

    }
}
2 4

Анализ на сложността за най-малката подмрежа с k разграничени числа  

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

О (п) където "н" е броят на елементите в масива.

Вижте също
Брой двойки, чиито продукти съществуват в масива

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

О (п) където "н" е броят на елементите в масива.