अ‍ॅरे मध्ये के घटकांमधील प्रथम घटक


अडचण पातळी सोपे
वारंवार विचारले ऍमेझॉन वाढ पीएयू एसएपी लॅब तेराडाटा विप्रो यात्रा Zoho
अरे हॅश

आम्ही संख्या 'के' आणि पूर्णांक अ‍ॅरे दिली आहे. अ‍ॅरेमध्ये के. वेळा आढळणा which्या अ‍ॅरेमधील पहिला घटक शोधण्यासाठी “अ‍ॅरे मध्ये प्रथम घटक” ही समस्या सांगते. अ‍ॅरे मध्ये कोणतेही घटक नसल्यास जे के वेळा येते तर परत -1.

उदाहरण

श्रेणीतील गहाळ घटक शोधा

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

स्पष्टीकरण

या उदाहरणात, दोन वेळा के वेळा आढळतात. 4 आणि 2 हे अचूकपणे किती वेळा अस्तित्वात आहेत, परंतु 4 वेळा के वेळा आढळते. तर आम्ही 4 परत करतो.

अल्गोरिदम

  1. घोषित ए हॅशमॅप.
  2. अ‍ॅरेचा आढावा घ्या.
    • नकाशामध्ये अ‍ॅरेच्या प्रत्येक घटकाची वारंवारता मोजा आणि संचयित करा.
  3. पुन्हा अ‍ॅरे ओलांडून तपासा आणि प्रत्येक अ‍ॅरे घटकाची वारंवारता के बरोबर आहे का ते तपासा.
    • जर अट पूर्ण झाली तर घटक परत करा.

स्पष्टीकरण

आपल्याकडे आमची इनपुट व्हॅल्यूज आहेत पूर्णांक अॅरे आणि पूर्णांक के. प्रॉब्लेम स्टेटमेंटमध्ये अ‍ॅरे मधील प्रथम घटक शोधण्यासाठी विचारले जाते जे के. या समस्येचे निराकरण करण्यासाठी आम्ही वापरणार आहोत हॅशिंग. हॅशिंग हा एक संभाव्य मार्ग आहे ज्याद्वारे आपण आपल्या वेळेची जटिलता कमी करू शकता. त्याला किंमत मोजावी लागेल O (n) वेळ गुंतागुंत.

आम्ही आमच्या नकाशामध्ये प्रत्येक घटकाची वारंवारिता मोजू आणि संग्रहित करू. समजा elementरेमध्ये एखादा घटक times वेळा आला तर त्या घटकासह आपण त्याची वारंवारता as म्हणून सेट केली. की आणि व्हॅल्यूज संचयित करण्यासाठी या हेतूसाठी हॅशमॅपचा वापर केला जाऊ शकतो. आम्ही हॅशमॅप मध्ये व्हॅल्यूज म्हणून सर्व घटक की आणि त्यांची वारंवारता संचयित करत आहोत. नंतर आपण एक लूप चालवू आणि अ‍ॅरेला मागे टाकू आणि प्रत्येक घटक निवडून त्यांची वारंवारता तपासू. जर कोणत्याही घटकाची वारंवारता के बरोबर असल्याचे आढळले तर आम्ही ते घटक परत करू. आपण अ‍ॅरेचा मागोवा घेत आहोत, म्हणून घटक घटना वेळासह आढळल्यास. तर नक्कीच घटना नसल्याचा हा पहिला घटक असेल.

चला त्याचं उदाहरण घेऊ:

अरे [] = {2,4,6,4,2,1,}, के = 2

नकाशामध्ये मूल्ये म्हणून आम्ही कीज आणि त्यांची वारंवारता घटक म्हणून संग्रहित करीत आहोत, आमचा नकाशा संचयित केल्यावर पुढील मूल्ये असतील:

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

आम्ही प्रत्येक अ‍ॅरे घटक तपासू, 0 व्या सूचीपासून आपण अ‍ॅरेचा शोध घेऊ

i = 0,

प्रत्येक अ‍ॅरेची वारंवारता असल्यास [i] == के:

२ ची फ्रिक्वेन्सी २ आहे, जी के बरोबर आहे आणि घटकाचा क्रमांक न घेता प्रथम येणारा घटक आहे, म्हणून आपण एरर परत करतो [i] आणि आपले आउटपुट २ असेल.

जर घटकाची कोणतीही वारंवारता 'के' शी जुळत नसेल तर आम्ही -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

अ‍ॅरेमध्ये के वेळा उद्भवणारा फर्स्ट एलिमेंट शोधण्यासाठी जावा कोड

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

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

O (n) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या. येथे आम्ही हॅशमॅप वापरल्यामुळे आम्ही ओ (1) वेळेत ऑपरेशन्स करण्यास सक्षम होतो.

स्पेस कॉम्प्लेक्सिटी

O (n) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या. सर्वात वाईट परिस्थितीत जेव्हा सर्व घटक वेगळे असतात. आम्हाला नकाशामध्ये सर्व एन घटक संचयित करावे लागतील जे रेषेची जागा घेतील.