መ ንጥሎችን ካስወገዱ በኋላ አነስተኛ ቁጥር ያላቸው የተለዩ አካላት  


የችግር ደረጃ መካከለኛ
ውስጥ በተደጋጋሚ ተጠየቀ ብላክ ሮክ ByteDance Expedia ኦላ ካብስ በ Oracle PayU የ SAP ላብራቶሪዎች Yandex
ሰልፍ ዛፍ

የችግሩ መግለጫ  

ችግሩ “የ m ንጥሎችን ካስወገዱ በኋላ አነስተኛ ቁጥር ያላቸው የተለዩ አካላት” አንድ እንዳለዎት ይገልጻል ደርድር እና ኢንቲጀር ኤም. እያንዳንዱ የድርድር አካል የንጥል መታወቂያውን ያሳያል። የችግሩ መግለጫ ቢያንስ የተለያዩ የመታወቂያ ግራዎች ቁጥር ሊኖር በሚችልበት መንገድ ኤም አባሎችን ለማስወገድ ይጠይቃል ፡፡

ለምሳሌ  

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

m=2
3

 

መ ንጥሎችን ካስወገዱ በኋላ አነስተኛ ቁጥር ያላቸው የተለዩ አካላትጭንቅላታም መያያዣ መርፌ

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

m=2
2

የ m ንጥሎችን ካስወገዱ በኋላ አነስተኛውን ልዩ ልዩ ንጥረ ነገሮችን ለማግኘት ስልተ ቀመር  

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

ማስረጃ

ኢንቲጀር ተሰጥቶናል ደርድር. ከተወገደ በኋላ በሚያስችል መንገድ የ m ንጥሎችን ብዛት የሚያስወግድ የችግር መግለጫ አለብን ፡፡ ስለዚህ ፣ አነስተኛ ቁጥር ያላቸው የተለዩ አባል መታወቂያዎች ሊኖሩን ይገባል ፡፡ የተለዩ አካላት የሆኑ 4 ቁጥሮች አሉን እና ሁለቱን ብናስወግድ እንበል ፡፡ አሁንም 2 የተለዩ አካላት አሉን ፣ ግን እዚህ ያለው ጉዳይ የተለየ ነው ፡፡ እኛ 4 የተለያዩ ቁጥሮች ካሉን የእነሱ ክስተት ለእያንዳንዱ ንጥረ ነገር ከአንድ በላይ ሊሆን ይችላል ፡፡ ከዚያ በኋላ አንድ አይነት ንጥረ ነገር ሁለት ጊዜ ወይም ምናልባትም ሁለት የተለያዩ አካላትን ማስወገድ እንችላለን ፣ ግን የኤም አካላት ከተወገዱ በኋላ የተለዩ አባላትን ብዛት መቀነስ አለብን ፡፡

ተመልከት
የአንድ አጠቃላይ ዛፍ ቁመት ከወላጅ ድርድር

ልንጠቀምበት ነው ማሳከክ. እኛ እናሳውቃለን ሃሽማፕ. የኬፕ እና የቴምብር እሴቶችን ወደ 0 በማቀናበር ድርድርን ማለፍ እና የእያንዳንዱን የድርጅት ብዛት ድግግሞሾችን በካርታው ውስጥ ማከማቸት እና እንጀምራለን። ምክንያቱም የእያንዳንዱን ንጥረ ነገር ድግግሞሽ ማወቅ አለብን ፡፡ ግን እሴቱን ለመጀመሪያ ጊዜ ካገኘን እየተጓዝን እያለ የኬፕ ዋጋን በ 1 ከፍ እናደርጋለን ፣ በመሠረቱ ፣ ለእኛ እንደ አቅም ወይም መጠን ይሠራል ፡፡

እኛ እያንዳንዱን የካርታ ቁልፍ እና እሴቶች እንደገና እንጎበኛለን ፣ በዚህ ጊዜ ማንኛውንም የካርታ ቁልፍ ከ m ያነሰ ወይም እኩል ከሆነ መፈለግ ያስፈልገናል ፣ ከዚያ የ m ዋጋን በቁልፍ ጊዜዎች መቀነስ ፣ መ እንደ ማዘመን አለብን ፡፡ m - ቁልፍ የቴምፕ ዋጋን አግኝቶ መጨመር። ይህ ሁኔታ የማያረካ ከሆነ በቃ እና በሙቀቱ መካከል ያለውን ልዩነት መመለስ ብቻ ያስፈልገናል ፡፡ በመጨረሻ እኛ መመለስ አለብን ካፕ-ቴምፕ፣ ምክንያቱም እያንዳንዱ ሁኔታ በከፊል ከሆነ የሚያሟላ ከሆነ የሚፈለገው ውጤት ነው ፣ ከዚያ የመመለሻ ተጨማሪ መግለጫ መስጠት አለብን።

ኮድ  

የ m ንጥሎችን ካስወገዱ በኋላ አነስተኛውን ልዩ ልዩ ንጥረ ነገሮችን ለማግኘት የ C ++ ኮድ

#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

የ 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

ውስብስብነት ትንተና  

የጊዜ ውስብስብነት

ኦ (N log N) ፣ ምክንያቱም ለጊዜ ውስብስብነት የላይኛው ወሰን ምልክት የሆነውን መደርደር ስለተጠቀምን ነው ፡፡

ተመልከት
በሁለትዮሽ ዛፍ ውስጥ አንድ መስቀለኛ መንገድ Inorder ተተኪ

የቦታ ውስብስብነት

ኦ (ኤን) ፣ ምክንያቱም እያንዳንዱን ንጥረ ነገር እንደ ቁልፍ እንጠቀም ነበር ፡፡ እኛ ማለት ይቻላል N አባሎች ሊኖሩን ይችላሉ።