Минималан број различитих елемената након уклањања м предмета


Ниво тешкоће Средњи
Често питани у Блацкроцк БитеДанце Екпедиа Ола Цабс пророчанство ПаиУ САП Лабс иандек
Ред Дрво

Изјава о проблему

Проблем „Минималан број различитих елемената након уклањања м ставки“ наводи да имате поредак и цео број м. Сваки елемент низа означава ИД-ове предмета. Изјава о проблему тражи уклањање м елемената на такав начин да остане минимални број различитих ИД-ова.

Пример

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

m=2
3

 

Минималан број различитих елемената након уклањања м предмета

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

Објашњење

Добијамо цео број поредак. Имамо изјаву о проблему која уклања м број елемената на такав начин да након уклањања. Дакле, требали бисмо имати минимални број различитих ИД-ова елемената. Претпоставимо да имамо 4 броја који су различити елементи и ако уклонимо два од њих. Још увек имамо два различита елемента, али случај овде је другачији. Ако имамо 2 различита броја, њихова појава може бити више од једног за сваки елемент. Тада исти елемент можемо уклонити два пута, или можда два различита елемента, али морамо смањити број различитих елемената након уклањања м елемената.

Користићемо хасхинг. Прогласићемо а Хасхмап. Постављањем вредности цап и темп на 0, започет ћемо обилазак низа и бројати и чувати фреквенције сваког елемента низа на мапи. То је зато што морамо знати учесталост сваког елемента. Али, док обилазимо ако вредност добијемо први пут, повећаћемо вредност ограничења за 1, у основи то нам одговара као капацитет или величина.

Поново ћемо посетити сваки кључ и вредности мапе, овог пута само треба да утврдимо да ли је било који кључ мапе мањи или једнак м, а затим смањимо вредност м за кључна времена, треба да ажурирамо м као м - кључ пронашли и повећали вредност темп. Ако овај услов не задовољава, само треба да вратимо разлику између ограничења и температуре. Напокон, морамо да вратимо цап-темп, јер је то потребан излаз ако сваки услов у неком делу задовољава, онда морамо да ставимо додатну изјаву о поврату.

код

Ц ++ код за проналажење минималног броја различитих елемената након уклањања м ставки

#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

Јава код за проналажење минималног броја различитих елемената након уклањања м ставки

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

Анализа сложености

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

О (Н лог Н), јер смо користили сортирање које означава горњу границу временске сложености.

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

НА), јер смо сваки елемент користили као кључ. Можемо имати скоро Н елемената.