এম আইটেমগুলি সরিয়ে নেওয়ার পরে স্বতন্ত্র উপাদানগুলির ন্যূনতম সংখ্যা


কাঠিন্য মাত্রা মধ্যম
প্রায়শই জিজ্ঞাসা করা হয় কালো শিলা ByteDance এক্সপিডিয়া ওলা ক্যাবস আকাশবাণী Payu এসএপি ল্যাব ইয়ানডেক্স
বিন্যাস গাছ

সমস্যা বিবৃতি

সমস্যা "মিটার আইটেমগুলি সরিয়ে নেওয়ার পরে স্বতন্ত্র উপাদানের ন্যূনতম সংখ্যা" উল্লেখ করে যে আপনার একটি রয়েছে বিন্যাস এবং একটি পূর্ণসংখ্যা মি। অ্যারের প্রতিটি উপাদান একটি আইটেম আইডির নির্দেশ করে। সমস্যার বিবৃতিটি এম উপাদানগুলিকে এমনভাবে সরিয়ে দিতে বলে যে সেখানে পৃথক আইডি বামের ন্যূনতম সংখ্যা থাকতে হবে।

উদাহরণ

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

জটিলতা বিশ্লেষণ

সময় জটিলতা

ও (এন লগ এন), কারণ আমরা বাছাই করেছি যা সময়ের জটিলতার জন্য উপরের সীমানা চিহ্নিত করে।

স্পেস জটিলতা ity

চালু), কারণ আমরা প্রতিটি উপাদানকে কী হিসাবে ব্যবহার করেছি। আমরা প্রায় এন উপাদান থাকতে পারে।