একটি অ্যারেতে সর্বোচ্চ এবং সর্বনিম্ন ফ্রিকোয়েন্সিগুলির মধ্যে পার্থক্য


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় দুর্গ প্রভূত ফোরকিটস Roblox টেসলা
বিন্যাস কাটা শ্রেণীবিভাজন

সমস্যাটি "একটি অ্যারের মধ্যে সর্বাধিক এবং সর্বনিম্ন ফ্রিকোয়েন্সিগুলির মধ্যে পার্থক্য" উল্লেখ করে যে ধরুন যে আপনার একটি রয়েছে পূর্ণসংখ্যা বিন্যাস। সমস্যার বিবৃতিটি একটি অ্যারেতে দু'টি পৃথক সংখ্যার সর্বাধিক ফ্রিকোয়েন্সি এবং সর্বনিম্ন ফ্রিকোয়েন্সিটির মধ্যে সর্বাধিক পার্থক্য জানতে চেয়েছে।

উদাহরণ

একটি অ্যারেতে সর্বোচ্চ এবং সর্বনিম্ন ফ্রিকোয়েন্সিগুলির মধ্যে পার্থক্য

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

ব্যাখ্যা

1 → 3 এর ফ্রিকোয়েন্সি (সর্বাধিক ফ্রিকোয়েন্সি)

5 → 1 এর ফ্রিকোয়েন্সি (সর্বনিম্ন ফ্রিকোয়েন্সি)

arr[] = {5, 4, 5, 5, 5, 3, 4 }
3

ব্যাখ্যা

5 → 4 এর ফ্রিকোয়েন্সি (সর্বাধিক ফ্রিকোয়েন্সি)

3 → 1 এর ফ্রিকোয়েন্সি (সর্বনিম্ন ফ্রিকোয়েন্সি)

অ্যালগরিদম

  1. ঘোষণা করুন ক মানচিত্র.
  2. একটি অ্যারের উপাদানটির ফ্রিকোয়েন্সি সঞ্চয় এবং গণনা করুন।
  3. সেট ম্যাক্সফ্রেইক থেকে 0 এবং minfreq থেকে n.
  4. মানচিত্রটি অতিক্রম করুন:
    1. মানচিত্রে ম্যাক্সফ্রেইক এবং ফ্রিকোয়েন্সিটির মধ্যে সর্বাধিক মানটি সন্ধান করুন এবং এটি ম্যাক্সফ্রেইকের কাছে সঞ্চয় করুন।
    2. মানচিত্রে minfreq এবং ফ্রিকোয়েন্সি মধ্যে ন্যূনতম মান সন্ধান করুন এবং এটি minfreq সংরক্ষণ করুন।
  5. রিটার্ন (ম্যাক্সফ্রেইক-মিনফ্রেইক)।

ব্যাখ্যা

আমরা পূর্ণসংখ্যার একটি অ্যারে আছে। আমাদের কাজটি হ'ল একটি অ্যারেতে উপস্থিত দুটি স্বতন্ত্র সংখ্যার সর্বাধিক উপস্থিতি এবং সর্বনিম্ন সংঘর্ষের মধ্যে সর্বাধিক পার্থক্যটি সন্ধান করা। আমরা ব্যবহার করতে যাচ্ছি হ্যাশ। এই প্রশ্নটি সমাধান করার জন্য হ্যাশিং একটি কার্যকর উপায় সরবরাহ করে। আমরা একটি মানচিত্র ঘোষণা করতে যাচ্ছি এবং প্রতিটি অ্যারের উপাদানগুলির ফ্রিকোয়েন্সি গণনা করতে এবং একই সাথে মানচিত্রে উপাদানগুলি সহ ফ্রিকোয়েন্সিগুলি সংরক্ষণ করে যাচ্ছি।

তারপরে আমরা এর মান নির্ধারণ করব ম্যাক্সফ্রেইক থেকে 0 এবং minfreq to n, অর্থাৎ অ্যারের দৈর্ঘ্য কারণ কোনও উপাদানের প্রদত্ত অ্যারের আকারের চেয়ে বেশি ফ্রিকোয়েন্সি নেই। আমরা মানচিত্রটি অতিক্রম করব এবং প্রতিটি উপাদান একে একে বেছে নেব এবং এটির ফ্রিকোয়েন্সি সর্বাধিক বা সর্বনিম্ন কিনা তা পরীক্ষা করব। সর্বাধিক ফ্রিকোয়েন্সিটি একটি ভিন্ন ভেরিয়েবল এবং ন্যূনতম ফ্রিকোয়েনিয়াকে বিভিন্ন ভেরিয়েবলে পৃথক করুন। আমাদের সর্বোচ্চ ফ্রিকোয়েন্সি এবং সর্বনিম্ন ফ্রিকোয়েন্সিগুলির মধ্যে পার্থক্যটি ফিরিয়ে আনতে হবে, সুতরাং আমরা ফিরে আসব (ম্যাক্সফ্রেইক-মিনফ্রেইক)।

চল একটি উদাহরণ দিই:

উদাহরণ

আরআর [] = {1, 2, 3, 1, 5, 2, 3, 1}

যখন আমরা প্রথমে অ্যারেটি অতিক্রম করব, আমরা মানকটিতে উপাদান এবং তাদের কোন উপস্থিতি রাখব না, ট্র্যাশিংয়ের পরে আমাদের মানচিত্রটি এইভাবে থাকবে:

মানচিত্র: {1: 3, 2: 2, 3: 2, 5: 1}

এখন, মানচিত্রে আমাদের প্রতিটি উপাদানগুলির উপস্থিতি রয়েছে, আমরা মানচিত্রটি অতিক্রম করতে যাচ্ছি, এবং মানচিত্রটি থেকে প্রতিটি উপাদান বাছাই করব এবং তাদের ফ্রিকোয়েন্সিটি পরীক্ষা করবো, যা বর্তমানের আরও বেশি ফ্রিকোয়েন্সি বা ম্যাক্সফ্রেইক এবং যা নূন্যতম বর্তমান ফ্রিকোয়েন্সি বা মিনিফ্রেইক এবং যথাক্রমে ম্যাক্সফ্রেইক এবং মিনফ্রেইকের কাছে সঞ্চয় করুন।

  • 1: 3 →

3 ম্যাক্সফ্রেইকের চেয়ে বড়, সুতরাং ম্যাক্সফ্রেইক = 3

3 মিনিফ্রেকের চেয়ে ছোট, সুতরাং মিনফ্রেইক = 3

  • 2: 2 →

ম্যাক্সফ্রেইক 2 এর চেয়ে বড়, তাই ম্যাক্সফ্রেইক = 3

2 মিনিফ্রেকের চেয়ে ছোট, সুতরাং মিনফ্রেইক = 2

  • 3: 2 →

ম্যাক্সফ্রেইক 2 এর চেয়ে বড়, তাই ম্যাক্সফ্রেইক = 3

মিনফেক, মিনফ্রেইক = 2 তে কিছুই পরিবর্তন হয় না

  • 5: 1 →

ম্যাক্সফ্রেইক 1 এর চেয়ে বড়, তাই ম্যাক্সফ্রেইক = 3

1 মিনিফ্রেকের চেয়ে ছোট, সুতরাং মিনফ্রেইক = 1

এবং আমরা maxfreq-minfreq → (3-1) = 2 এর মধ্যে পার্থক্যটি ফিরিয়ে দেব।

কোড

অ্যারেতে সর্বোচ্চ এবং সর্বনিম্ন ফ্রিকোয়েন্সিগুলির মধ্যে পার্থক্য খুঁজতে সি ++ কোড

#include<iostream>
#include<unordered_map>

using namespace std;

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

    int maxfreq = 0, minfreq = n;
    for (auto x : freq)
    {
        maxfreq = max(maxfreq, x.second);
        minfreq = min(minfreq, x.second);
    }
    return (maxfreq - minfreq);
}
int main()
{
    int arr[] = {1, 2, 3, 1, 5, 2, 3, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << getMaximumDiff(arr, n) << "\n";
    return 0;
}
2

অ্যারেতে সর্বোচ্চ এবং সর্বনিম্ন ফ্রিকোয়েন্সিগুলির মধ্যে পার্থক্য খুঁজে পাওয়ার জন্য জাভা কোড

import java.util.HashMap;
import java.util.Map;

class diffBWHighFLeastF
{
    public static int getMaximumDiff(int arr[], int n)
    {
        HashMap<Integer,Integer> freq = new HashMap<>();
        for (int i = 0 ; i < n; i++)
        {
            if(freq.containsKey(arr[i]))
            {
                freq.put(arr[i], freq.get(arr[i])+1);
            }
            else
            {
                freq.put(arr[i], 1);
            }
        }
        int maxfreq = 0, minfreq = n;
        for (Map.Entry<Integer,Integer> x : freq.entrySet())
        {
            maxfreq = Math.max(maxfreq, x.getValue());
            minfreq = Math.min(minfreq, x.getValue());
        }
        return (maxfreq - minfreq);
    }
    public static void main(String[] args)
    {
        int arr[] = {1, 2, 3, 1, 5, 2, 3, 1 };
        int n = arr.length;
        System.out.println(getMaximumDiff(arr, n));
    }
}
2

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

সময় জটিলতা

উপর) কোথায় "এন" অ্যারেতে উপাদানগুলির সংখ্যা। এখানে আমরা কেবল অ্যারেগুলির উপাদানগুলির উপর তাদের ফ্রিকোয়েন্সিগুলির উপর নজর রাখছি tra এই সমস্তগুলির জন্য কেবল ও (এন) সময় ব্যয় হয়।

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

উপর) কোথায় "এন" অ্যারেতে উপাদানগুলির সংখ্যা। সর্বোপরি, আমরা n উপাদানগুলি সবগুলিতে স্বতন্ত্র থাকলে সঞ্চয় করতে পারি। স্থান জটিলতা রৈখিক।