Առանձնացված տարրերի նվազագույն քանակը m կետերը հեռացնելուց հետո


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են Blackrock ByteDance Expedia Օլա Քաբս Պատգամախոս PayU SAP լաբորատորիաներ Yandex
Դասավորություն ծառ

Խնդիրի հայտարարություն

«Առանձնացված տարրերի նվազագույն քանակը m կետերը հեռացնելուց հետո» խնդիրը նշում է, որ դուք ունեք ան դասավորություն և ամբողջ մ. Rayանգվածի յուրաքանչյուր տարր նշում է իրի id- ները: Խնդրի հայտարարությունը խնդրում է m տարրերը հեռացնել այնպես, որ մնա հստակ ID- ի նվազագույն քանակ:

Օրինակ

arr[] = {1, 3, 4, 2, 4, 1, 3 }

m=2
3

 

Առանձնացված տարրերի նվազագույն քանակը m կետերը հեռացնելուց հետո

arr[] = {1, 4, 4, 1}

m=2
2

Մ տարրերը հեռացնելուց հետո հստակ տարրերի նվազագույն քանակը գտնելու ալգորիթմ

1. Declare a map.
2. Set temp to 0.
3. Count and store the frequencies of each element of the array into the map and check how many unique keys are present in it and set it as a cap.
4. Traverse the map and check if the key element is less than or equal to m.
    1. If true then decrease the value of m up to that key and also increase the temp by 1.
    2. Else return cap-temp.
5. Return cap-temp

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

Մեզ տրվում է ամբողջ թիվ դասավորություն, Մենք ունենք խնդրի հայտարարություն, որը հեռացնում է մ քանակի տարրերը այնպես, որ հեռացումից հետո: Այսպիսով, մենք պետք է ունենանք տարրերի հստակ ID- ների նվազագույն քանակ: Ենթադրենք, որ մենք ունենք 4 թվեր, որոնք հստակ տարրեր են, և եթե դրանցից երկուսը հանենք: Մենք դեռ ունենք 2 հստակ տարր, բայց դեպքն այստեղ այլ է: Եթե ​​մենք ունենք 4 տարբեր թվեր, դրանց առաջացումը կարող է լինել մեկից ավելի յուրաքանչյուր տարրի համար: Այդ դեպքում մենք կարող ենք նույն տարրը երկու անգամ հեռացնել, կամ գուցե երկու տարբեր տարրեր, բայց մենք պետք է նվազագույնի հասցնենք հստակ տարրերի քանակը m տարրերի հեռացումից հետո:

Մենք պատրաստվում ենք օգտագործել ծիծաղել, Մենք կհայտարարենք ա Հաշմապ, Սահմանելով գլխարկի և տեմպի արժեքները 0-ի վրա, մենք կսկսենք թերթել զանգվածը և հաշվել և պահպանել քարտեզի մեջ յուրաքանչյուր զանգվածի տարրի հաճախականությունները: Դա այն պատճառով է, որ մենք պետք է իմանանք յուրաքանչյուր տարրի հաճախականությունը: Բայց, երթևեկելով, եթե արժեքն առաջին անգամ ստանանք, կափարիչի արժեքը կբարձրացնենք 1-ով, հիմնականում դա մեզ համար աշխատում է որպես հզորություն կամ չափ:

Մենք նորից կայցելենք քարտեզի յուրաքանչյուր բանալին և արժեքները, այս անգամ պարզապես պետք է պարզենք, թե քարտեզի որևէ բանալի փոքր է կամ հավասար է m- ի, ապա m- ի արժեքը նվազեցրու ենք ըստ հիմնական ժամանակների, պետք է m- ն թարմացնել որպես m - բանալին գտել և բարձրացնել տեմպի արժեքը: Եթե ​​այս պայմանը չի բավարարում, մենք պարզապես պետք է վերադարձնենք գլխարկի և տեմպի տարբերությունը: Վերջապես, մենք պետք է վերադարձնենք այն գլխարկ-տեմպ, քանի որ դա անհրաժեշտ արդյունքն է, եթե յուրաքանչյուր պայման բավարարում է եթե մաս է, ապա մենք պետք է դնենք վերադարձի լրացուցիչ հայտարարություն:

Կոդ

C ++ կոդ ՝ m տարրերը հեռացնելուց հետո հստակ տարրերի նվազագույն քանակը գտնելու համար

#include<iostream>
#include<unordered_map>
#include<vector>
#include<algorithm>

using namespace std;

int getMinimumDistinctIds(int arr[], int n, int m)
{
    unordered_map<int, int> MAP;
    vector<pair<int, int> > vec;
    int temp = 0;

    for (int i = 0; i < n; i++)
        MAP[arr[i]]++;

    for (auto it = MAP.begin(); it != MAP.end(); it++)
        vec.push_back(make_pair(it->second, it->first));

    sort(vec.begin(), vec.end());

    int cap = vec.size();

    for (int i = 0; i < cap; i++)
    {
        if (vec[i].first <= m)
        {
            m = m - vec[i].first;
            temp++;
        }
        else
            return cap - temp;
    }
    return cap - temp;
}
int main()
{
    int arr[] = { 1, 3, 4, 2, 4, 1, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int m = 2;
    cout << getMinimumDistinctIds(arr, n, m);
    return 0;
}
3

Java կոդ ՝ m տարրերը հեռացնելուց հետո հստակ տարրերի նվազագույն քանակը գտնելու համար

import java.util.Map.Entry;
import java.util.Map;
import java.util.HashMap;


class MinimumDistinctId
{
    public static int getMinimumDistinctIds(int arr[], int n, int m)
    {
        Map<Integer, Integer> MAP = new HashMap<Integer, Integer>();
        int temp = 0;
        int cap = 0;
        for (int i = 0; i < n; i++)
        {
            if (MAP.containsKey(arr[i]) == false)
            {
                MAP.put(arr[i], 1);
                cap++;
            }
            else
                MAP.put(arr[i], MAP.get(arr[i]) + 1);
        }
        for (Entry<Integer, Integer> entry:MAP.entrySet())
        {
            if (entry.getKey() <= m)
            {
                m = m - entry.getKey();
                temp++;
            }
            else
                return cap - temp;
        }
        return cap - temp;
    }
    public static void main(String[] args)
    {
        int arr[] = {1, 3, 4, 2, 4, 1, 3};
        int m = 2;
        System.out.println(getMinimumDistinctIds(arr, arr.length, m));
    }
}
3

Բարդության վերլուծություն

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

O (N տեղեկագիր N), քանի որ մենք օգտագործել ենք տեսակավորում, որը նշում է ժամանակի բարդության վերին սահմանը:

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

ՎՐԱ), քանի որ յուրաքանչյուր տարր օգտագործում էինք որպես բանալի: Մենք կարող ենք ունենալ գրեթե N տարրեր: