એમ વસ્તુઓ દૂર કર્યા પછી વિશિષ્ટ તત્વોની ન્યૂનતમ સંખ્યા  


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે બ્લેકરોક ByteDance એક્સપેડિયા ઓલા કેબ્સ ઓરેકલ પે એસએપી લેબ્સ યાન્ડેક્ષ
અરે વૃક્ષ

સમસ્યા નિવેદન  

સમસ્યા "એમ આઇટમ્સને દૂર કર્યા પછી વિશિષ્ટ તત્વોની ન્યૂનતમ સંખ્યા" જણાવે છે કે તમારી પાસે એક એરે અને પૂર્ણાંક એમ. એરેનો દરેક તત્વ આઇટમ આઇડી સૂચવે છે. સમસ્યાનું નિવેદન એમ તત્વોને એવી રીતે દૂર કરવા કહે છે કે અલગ અલગ આઈડીની ડાબી સંખ્યા ઓછામાં ઓછી હોવી જોઈએ.

ઉદાહરણ  

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

સમજૂતી

આપણને પૂર્ણાંક આપવામાં આવે છે એરે. અમારી પાસે સમસ્યાનું નિવેદન છે, જે એમ નંબરની સંખ્યાને એવી રીતે દૂર કરે છે કે દૂર કર્યા પછી. તેથી, અમારી પાસે અલગ અલગ તત્વ IDની ન્યૂનતમ સંખ્યા હોવી જોઈએ. ધારો કે આપણી પાસે 4 સંખ્યાઓ છે જે વિશિષ્ટ તત્વો છે અને જો આપણે તેમાંથી બે કા removeીએ છીએ. અમારી પાસે હજી પણ 2 અલગ તત્વો છે, પરંતુ અહીં કેસ જુદો છે. જો આપણી પાસે 4 જુદા જુદા નંબરો છે, તો તેમની ઘટક દરેક તત્વ માટે એક કરતા વધુ હોઈ શકે છે. પછી આપણે એક જ તત્વને બે વાર, અથવા કદાચ બે જુદા જુદા તત્વોને દૂર કરી શકીએ છીએ, પરંતુ એમ તત્વોને દૂર કર્યા પછી આપણે અલગ તત્વોની ગણતરી ઘટાડવી પડશે.

આ પણ જુઓ
પિતૃ એરેથી સામાન્ય ઝાડની .ંચાઈ

આપણે વાપરવા જઈ રહ્યા છીએ હેશીંગ. અમે જાહેર કરીશું a હાશમpપ. કેપ અને ટેમ્પની કિંમતોને 0 પર સેટ કરીને, આપણે એરેને ટ્રversવર્સ કરવાનું શરૂ કરીશું અને દરેક એરે એલિમેન્ટની આવર્તનને નકશામાં ગણી અને સંગ્રહ કરીશું. આ એટલા માટે છે કે આપણે દરેક તત્વની આવર્તન જાણવાની જરૂર છે. પરંતુ, જ્યારે આપણને પ્રથમ વખત મૂલ્ય મળે તો તે ટ્રversવર્સ કરતી વખતે, અમે કેપનું મૂલ્ય 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

જટિલતા વિશ્લેષણ  

સમય જટિલતા

ઓ (એન લોગ એન), કારણ કે આપણે સingર્ટિંગનો ઉપયોગ કર્યો છે જે સમયની જટિલતા માટે ઉપલા બાઉન્ડને ચિહ્નિત કરે છે.

આ પણ જુઓ
બાઈનરી ટ્રીમાં નોડનો આંતરિક ક્રમિક

અવકાશ જટિલતા

ઓ (એન), કારણ કે આપણે દરેક તત્વનો ઉપયોગ કી તરીકે કર્યો છે. આપણી પાસે લગભગ N તત્વો હોઈ શકે છે.