অ্যারে একই উপাদানগুলির সমস্ত উপাদান তৈরি করতে সর্বনিম্ন অপারেশনগুলি মুছুন


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় রৌদ্রপক্ব ইষ্টক ফ্যাক্সেট
বিন্যাস কাটা

ধরুন আমাদের একটি ইনপুট আছে বিন্যাস সঙ্গে "এক্স" উপাদান সংখ্যা। আমরা একটি সমস্যা দিয়েছি যে আমাদের মুছে ফেলা অপারেশনগুলি সন্ধান করতে হবে, এটি ন্যূনতম হওয়া উচিত যা সমান অ্যারে তৈরি করতে হবে অর্থাৎ অ্যারেটি সমান উপাদানগুলি নিয়ে গঠিত।

উদাহরণ

ইনপুট:

[1, 1, 4, 6, 2, 1]

আউটপুট:

3

ব্যাখ্যা:

(4, 6, 2) 3 টি উপাদান অপসারণের পরে অ্যারে সমান হয়ে যায়, [1, 1, 1]

ইনপুট:

[1, 5, 4, 16, 32, 9]

আউটপুট:

5

ব্যাখ্যা:

এটি একটি সমান অ্যারে করতে আমরা 5 টি উপাদানের যে কোনওটিকে সরাতে পারি।

অ্যালগরিদম

  1. অ্যারে সমস্ত উপাদানগুলির ফ্রিকোয়েন্সি একটি মানচিত্রে সংরক্ষণ করুন।
  2. সেট "সর্বাধিক_ফ্রেক" থেকে INT_MIN.
  3. মানচিত্রের উপরে পরিবেশন করুন এবং কোন উপাদানটির সর্বাধিক ফ্রিকোয়েন্সি রয়েছে তা পরীক্ষা করুন।
    • সেট "সর্বাধিক_ফ্রেক" থেকে সর্বাধিক (সর্বোচ্চ_ফ্রেক, মান) সমস্ত ফ্রিকোয়েন্সিগুলির মধ্যে সর্বাধিক মান সন্ধান করতে।
  4. অ্যারের আকারের মধ্যে পার্থক্যটি ফিরিয়ে দিন "এন" এবং সর্বোচ্চ_ফ্রেক (এন - ম্যাক্স_ফ্রেक).

ব্যাখ্যা

আমরা একটি সমস্যা দিয়েছি যার মধ্যে আমাদের ন্যূনতম কতটি খুঁজে বের করতে হবে মুছিয়াতা অপারেশনগুলির জন্য একটি অ্যারে সমান (একই উপাদানগুলির) তৈরি করা প্রয়োজন। এই জন্য, আমরা সঞ্চয় করতে একটি মানচিত্র ব্যবহার করতে যাচ্ছি ফ্রিকোয়েন্সি অ্যারে উপস্থিত প্রতিটি সংখ্যার।

এটি করে, আমাদের সেই ফ্রিকোয়েন্সি থাকবে যা সমস্ত ফ্রিকোয়েন্সিগুলির মধ্যে বৃহত্তম। মানচিত্রে পুনরাবৃত্তি করার মাধ্যমে আমরা সর্বোচ্চ পদ্ধতিটি ব্যবহার করে সেই সর্বাধিক ফ্রিকোয়েন্সি পেতে পারি। পুনরাবৃত্তি পরে মানচিত্র আমাদের সর্বাধিক ফ্রিকোয়েন্সি থাকবে এবং আমাদের অ্যারে_ সাইজ - সর্বোচ্চ ফ্রিকোয়েন্সি ফিরে আসতে হবে, এর অর্থ আমরা অ্যারে সমান করতে মোট কম ফ্রিকোয়েন্সিগুলি ফিরিয়ে আনছি যা সরানো যেতে পারে।

আসুন একটি উদাহরণ বিবেচনা করুন:

আরআর: {10, 3, 4, 4, 2, 4};

  • i = 0, এটি আর [i] 10 হিসাবে এবং স্টোর ফ্রিক (10, 1) লাগে।
  • i = 1, এটি আর [i] 3 হিসাবে এবং স্টোর ফ্রিক (3, 1) লাগে।
  • i = 2 এর জন্য এটি আরআর [i] 4 এবং স্টোর ফ্রিক (4, 1) হিসাবে লাগে।
  • i = 3, এটি 4 হিসাবে arr লাগে [i], যেহেতু 4 এর মানচিত্রে ইতিমধ্যে একটি জায়গা রয়েছে এটি 4 এর মূল স্থানে আরও একটি গণনা যুক্ত করে এবং স্টোর ফ্রিক (4, 2)।
  • i = 4, এটি আর [i] হিসাবে 2 এবং স্টোর ফ্রিক (2, 1) লাগে।
  • i = 5 এর জন্য এটি আরআর লাগে [i] 4 হিসাবে, যেহেতু 4 একটি মানচিত্রে ইতিমধ্যে একটি জায়গা রয়েছে এটি 4 এর মূল স্থানে আরও একটি গণনা যুক্ত করে এবং স্টোর ফ্রিক (4, 3)।

এই সমস্তমাত্র '4' এর মধ্যে সর্বাধিক ফ্রিকোয়েন্সি রয়েছে যা 3 হয় এবং মানচিত্র থেকে 3 হিসাবে সর্বাধিক ফ্রিকোয়েন্সিটি সন্ধান এবং সন্ধানের পরে, আমরা মানটি ফেরত যাচ্ছি (n - max_freq) ৩. এটি আমাদের আউটপুট।

বাস্তবায়ন

অ্যারে একই উপাদানের সমস্ত উপাদান তৈরি করতে সর্বনিম্ন মুছুন অপারেশনগুলির জন্য সি ++ প্রোগ্রাম

#include <bits/stdc++.h>
using namespace std;

int minDelete(int arr[], int n)
{
    unordered_map<int, int> freq;
    for (int i = 0; i < n; i++)
        freq[arr[i]]++;

    int max_freq = INT_MIN;

    for (auto itr = freq.begin(); itr != freq.end(); itr++)
        max_freq = max(max_freq, itr->second);

    return n - max_freq;
}
int main()
{
    int arr[] = { 10, 3, 4, 4, 2, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << minDelete(arr, n);
    return 0;
}
3

অ্যারে একই উপাদানগুলির সমস্ত উপাদান তৈরি করতে সর্বনিম্ন মুছুন অপারেশনগুলির জন্য জাভা প্রোগ্রাম

import java.util.HashMap;
class minimumDeletionOperation
{
    public static int noOfMinimumDeletions(int arr[], int n)
    {
        HashMap<Integer,Integer> freq=new HashMap<Integer,Integer>();
        for(int i=0; i<arr.length; i++)
        {
            if(freq.containsKey(arr[i]))
                freq.put(arr[i], freq.get(arr[i]) + 1);
            else
                freq.put(arr[i], 1);
        }

        int max_freq=Integer.MIN_VALUE;

        for (int i:freq.keySet())
            max_freq = Math.max(max_freq, freq.get(i));

        return n - max_freq;
    }
    public static void main(String args[])
    {
        int arr[] = { 10, 3, 4, 4, 2, 4 };
        int n = arr.length;
        System.out.println(noOfMinimumDeletions(arr, n));
    }
}
3

অ্যারে একই উপাদানগুলির সমস্ত উপাদান তৈরি করতে সর্বনিম্ন মুছুন অপারেশনগুলির জন্য জটিলতা বিশ্লেষণ

সময় জটিলতা

ও (এন) যেখানে "এন" অ্যারেতে উপাদানগুলির সংখ্যা

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

ও (এন) যেখানে "এন" অ্যারেতে উপাদানগুলির সংখ্যা