Ամենափոքր ենթաշերտը k հստակ թվերով


Դժվարության մակարդակ Դժվար
Հաճախակի հարցնում են Amazon Google
Դասավորություն Խանգարել Սահող պատուհան Երկու ցուցիչ

Ենթադրենք, դուք ունեք ամբողջ թիվ դասավորություն և մի շարք k: Խնդրի հայտարարությունը խնդրում է պարզել ընդգրկույթի (l, r) ներառյալ ամենափոքր ենթաշղթան, այդպիսով, այդ ամենափոքր ենթաշղթայում առկա են ճիշտ k տարբեր թվեր:

Օրինակ

Մուտք:

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

k = 3

Արդյունք:

2, 4

Բացատրությունը.

{2, 3, 4} - ը ամենափոքր ենթաշարքն է ՝ սկսած 2-իցnd ինդեքսը `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. Այլապես, տպիր ձախ կողմի և աջ կողմի արժեքները:

բացատրություն

Storeանգվածը դիտելիս պահեք զանգվածի տարրերի յուրաքանչյուր հաճախականությունը և ընտրեք զանգվածի յուրաքանչյուր տարր և ստուգեք, արդյոք քարտեզի չափը k- ից պակաս է, եթե պարզվում է, որ k- ից պակաս է, քան մենք պետք է հաշվենք և պահենք այդ զանգվածի տարրի հաճախականությունը, և արդյոք Քարտեզի չափը գտնում է, որ k է (տարրի հստակ տարր) և ներկայիս երկարությունը պակաս է ենթադասի նախորդ երկարությունից, ապա մենք կթարմացնենք ձախ կողմի և աջ կողմի ցուցիչները: Այս ամենը կընթանա օղակում, մինչև որ ամբողջ քարտեզը մեկ անգամ անցնի:

Եթե ​​պարզվում է, որ քարտեզի չափը k- ից պակաս է, ապա կոտրիր: Մենք արժեքները ստացել ենք քարտեզի վրա: Օղակը գնալու է այնքան ժամանակ, քանի դեռ պարզվել է, որ քարտեզի չափը հավասար է k- ին, պարզվում է, որ զանգվածի տարրերի հաճախությունը քարտեզում հավասար է 1-ի, ապա մենք պետք է այդ որոշակի տարրը հանենք քարտեզից, այլապես պետք է նվազեցնել քարտեզից այդ որոշակի տարրի հաճախականությունը: Կրկին մենք պատրաստվում ենք ստուգել, ​​արդյոք քարտեզի չափը հավասար է k- ին, և ներկայիս ենթախմբի երկարությունը պակաս է նախկինում թարմացված երկարությունից, ապա թարմացրեք ձախ կողմի և աջ կողմի ցուցիչները: Եթե ​​զանգվածի տարրի հաճախականությունը 1 է, ապա այդ էլեմենտը հանիր, ևս տարրերի հաճախականությունը իջեցրու:

Rayանգվածի անցումից հետո, եթե պարզվի, որ ձախ կողմի ցուցիչը 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 հստակ թվերով

Timeամանակի բարդություն

O (n) որտեղ «Ն» զանգվածում տարրերի քանակն է:

Տիեզերական բարդություն

O (n) որտեղ «Ն» զանգվածում տարրերի քանակն է: