K ерекше сандары бар ең кіші ішкі массив


Күрделілік дәрежесі қиын
Жиі кіреді Amazon Google
Array Hash Сырғымалы терезе Екі көрсеткіш

Сізде бүтін сан бар делік массив және k саны. Есептер (l, r) диапазонының ең кіші жиымын табуды сұрайды, осылайша ең кіші жиымда нақты k нақты сандар болады.

мысал

Кіру:

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

k = 3

Шығару:

2, 4

Түсіндіру:

{2, 3, 4} - 2-ден басталатын ең кіші жиымnd индексі 4-ке дейінth 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. Басқа жағынан, сол және оң жақ мәндерін басып шығарыңыз.

Түсіндіру

Массивті жүріп өткен кезде әрбір жиым элементтерінің жиілігін сақтаңыз және массивтің әр элементін таңдап алыңыз, егер картаның өлшемі k-ден аз болса, егер біз ол жиым элементінің жиілігін санап, сақтауымыз керек болса, егер картаның өлшемі k деп анықталды (элементтің нақты нөмірі), сонымен қатар ағымдағы ұзындық ішкі жиымның алдыңғы ұзындығынан аз, содан кейін сол және оң жақ көрсеткіштерді жаңартамыз. Мұның бәрі бүкіл карта бір рет өтпейінше, циклде болады.

Егер картаның өлшемі k-ден аз болса, онда үзіліс жасаңыз. Біз картада мәндерді алдық. Цикл картаның өлшемі k-ге тең болғанша, массив элементінің жиілігі 1-ге тең болғанға дейін жүреді, содан кейін біз бұл элементті картадан алып тастауымыз керек, әйтпесе кішірейту керек нақты элементтің картадан жиілігі. Тағы да біз картаның өлшемі k-ге тең екенін және ағымдағы ішкі массивтің ұзындығы бұрын жаңартылған ұзындықтан аз екенін тексереміз, содан кейін сол жақ және оң жақ көрсеткіштерді жаңартыңыз. Егер жиым элементінің жиілігі 1-ге тең болса, онда бұл элементті алып тастаңыз, элементтің жиілігін азайтыңыз.

Массивті кесіп өткеннен кейін, егер сол жақтағы көрсеткіш 0, ал оң жақтағы көрсеткіштен n деп табылса, онда ол жарамсыз k дегенді білдіреді. Басқасы сол және оң жақ көрсеткіштің мәнін басып шығарады, ол ең кіші жиымның басталатын және аяқталатын нүктесі болады.

Іске асыру

K нөмірі бар ең кіші қосалқы терезеге арналған C ++ бағдарламасы

#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

K ерекше сандары бар ең кіші қосалқы терезеге арналған Java бағдарламасы

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 ерекше сандары бар ең кіші ішкі массивтің күрделілігін талдау

Уақыттың күрделілігі

O (N) қайда «N» - бұл массивтегі элементтер саны.

Ғарыштың күрделілігі

O (N) қайда «N» - бұл массивтегі элементтер саны.