অ্যারেতে কে এল বারের প্রথম উপাদান


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় মর্দানী স্ত্রীলোক আরোহণ Payu এসএপি ল্যাব তেরদাটা উইপ্রো রথযাত্রা Zoho
বিন্যাস কাটা

আমরা একটি সংখ্যা 'কে' এবং একটি পূর্ণসংখ্যা অ্যারে দিয়েছি। অ্যারেতে প্রথম উপাদানটি "অ্যারেতে কে-বার সংঘটিত হওয়া" সমস্যাটি অ্যারের প্রথম উপাদানটি খুঁজে বের করতে বলে যা অ্যারেতে ঠিক কে বার দেখা দেয়। অ্যারেতে যদি কোন উপাদান থাকে যা কে বার হয় তবে -1 ফিরে আসুন।

উদাহরণ

একটি ব্যাপ্তির উপাদান অনুপস্থিত খুঁজুন

Arr[]={1,4,5,2,4,2,7},  k=2
4

ব্যাখ্যা

এই উদাহরণে, দুটি সময় যা কে সময়ে ঘটে। 4 এবং 2 হুবহু k সংখ্যকবারের অস্তিত্ব রয়েছে, তবে 4 টি কে-টাইমের সাথে প্রথম হয়। সুতরাং আমরা 4 ফিরে।

অ্যালগরিদম

  1. ঘোষণা করুন ক হ্যাশ মানচিত্র.
  2. অ্যারে অতিক্রম করুন।
    • মানচিত্রে অ্যারের প্রতিটি উপাদানের ফ্রিকোয়েন্সি গণনা করুন এবং সংরক্ষণ করুন।
  3. আবার অ্যারে অতিক্রম করুন এবং পরীক্ষা করুন যে প্রতিটি অ্যারের উপাদানটির ফ্রিকোয়েন্সি k এর সমান কিনা।
    • যদি শর্তটি সন্তুষ্ট হয়, তবে উপাদানটি ফিরিয়ে দিন।

ব্যাখ্যা

আমাদের হিসাবে আমাদের ইনপুট মান আছে পূর্ণসংখ্যা বিন্যাস এবং একটি পূর্ণসংখ্যা কে। সমস্যা বিবরণী ঠিক অ্যারে টাইমে ঘটে এমন অ্যারেতে প্রথম উপাদানটি খুঁজতে বলে। এই সমস্যাটি সমাধান করার জন্য, আমরা ব্যবহার করতে যাচ্ছি হ্যাশ। হ্যাশিং হ'ল সম্ভাব্য উপায় যার মাধ্যমে আমরা আমাদের সময়ের জটিলতা হ্রাস করতে পারি। খরচ উপর) সময়ের জটিলতা

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

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

অ্যারে [] = {2,4,6,4,2,1,}, কে = 2

মানচিত্রের মান হিসাবে আমরা কী এবং তাদের ফ্রিকোয়েন্সি হিসাবে উপাদানগুলি সংরক্ষণ করব, আমাদের মানচিত্র সংরক্ষণের পরে নিম্নলিখিত মানগুলি থাকবে:

myMap={1:1, 2:2, 4:2, 6:1};

আমরা প্রতিটি অ্যারে উপাদান চেক করব, 0 তম সূচক থেকে শুরু করে আমরা অ্যারেটিকে অনুসরণ করতে শুরু করব

i = 0,

যদি প্রতিটি অ্যারের ফ্রিকোয়েন্সি [i] == কে:

2 এর ফ্রিকোয়েন্সি 2 হ'ল, যা k এর সমান এবং এটি উপাদান যা কে এর সাথে প্রথমদিকে আসে না, সুতরাং আমরা আরআরটি ফিরিয়ে দেব [i] এবং আমাদের আউটপুট 2 হবে।

যদি কোনও উপাদানটির ফ্রিকোয়েন্সি 'কে' এর সাথে মেলে না, তবে আমরা ফিরে আসব -1।

কোড

অ্যারেতে প্রথমবারের জন্য এল উপাদানটি খুঁজে পেতে সি ++ কোড

#include<iostream>
#include <unordered_map>

using namespace std;

int firstElement(int arr[], int n, int k)
{
    unordered_map<int, int> freqMap;

    for (int i=0; i<n; i++)
        freqMap[arr[i]]++;

    for (int i=0; i<n; i++)
        if (freqMap[arr[i]] == k)
            return arr[i];

    return -1;
}
int main()
{
    int arr[] = {2,4,6,4,2,1,6};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;
    cout << firstElement(arr, n, k);
    return 0;
}
2

একটি অ্যারেতে k বার সংঘটিত প্রথম উপাদানটি খুঁজে পেতে জাভা কোড

import java.util.HashMap;

class firstKOccuringElement
{
    public static int getFirstElement(int arr[], int n, int k)
    {
        HashMap<Integer, Integer> freqMap = new HashMap<>();
        for (int i = 0; i < n; i++)
        {
            int a = 0;
            if(freqMap.containsKey(arr[i]))
            {
                freqMap.put(arr[i], freqMap.get(arr[i])+1);
            }
            else
            {
                freqMap.put(arr[i], 1);
            }
        }
        for (int i = 0; i < n; i++)
        {
            if (freqMap.get(arr[i]) == k)
            {
                return arr[i];
            }
        }
        return -1;
    }
    public static void main(String[] args)
    {
        int arr[] = {2,4,6,4,2,1,6};
        int n = arr.length;
        int k = 2;
        System.out.println(getFirstElement(arr, n, k));
    }
}
2

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

সময় জটিলতা

উপর) কোথায় "এন" অ্যারেতে উপাদানগুলির সংখ্যা। এখানে, যেহেতু আমরা একটি হ্যাশম্যাপ ব্যবহার করেছি আমরা ও (1) সময়ে অপারেশন করতে সক্ষম হয়েছি।

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

উপর) কোথায় "এন" অ্যারেতে উপাদানগুলির সংখ্যা। সবচেয়ে খারাপ ক্ষেত্রে যখন সমস্ত উপাদান পৃথক হয়। আমাদের সমস্ত এন উপাদানগুলিকে মানচিত্রে সংরক্ষণ করতে হবে যা লিনিয়ার স্পেস নেবে।