एम आइटम हटाने के बाद विभिन्न तत्वों की न्यूनतम संख्या


कठिनाई स्तर मध्यम
में अक्सर पूछा ब्लैकरॉक ByteDance Expedia ओला कैब ओरेकल PayU एसएपी लैब्स Yandex
ऐरे पेड़

समस्या का विवरण

समस्या "एम आइटम हटाने के बाद विभिन्न तत्वों की न्यूनतम संख्या" बताती है कि आपके पास ए सरणी और एक पूर्णांक मी। सरणी का प्रत्येक तत्व एक आइटम आईडी इंगित करता है। समस्या कथन एम तत्वों को इस तरह से हटाने के लिए कहता है कि न्यूनतम आईडी की बाईं ओर न्यूनतम संख्या होनी चाहिए।

उदाहरण

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 अलग तत्व हैं, लेकिन यहां मामला अलग है। यदि हमारे पास 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

एम कोड हटाने के बाद विभिन्न तत्वों की न्यूनतम संख्या ज्ञात करने के लिए जावा कोड

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

जटिलता विश्लेषण

समय जटिलता

ओ (एन लॉग एन), क्योंकि हमने छँटाई का उपयोग किया है जो समय की जटिलता के लिए ऊपरी सीमा को चिह्नित करता है।

अंतरिक्ष जटिलता

पर), क्योंकि हमने प्रत्येक तत्व को कुंजी के रूप में उपयोग किया है। हमारे पास लगभग एन तत्व हो सकते हैं।