किसी एरे में k समय में होने वाला पहला तत्व


कठिनाई स्तर आसान
में अक्सर पूछा वीरांगना वृद्धि PayU एसएपी लैब्स Teradata विप्रो यात्रा Zoho
ऐरे हैश

हमने एक संख्या 'k' और एक पूर्णांक सरणी दी है। समस्या "सरणी में k समय में होने वाला पहला तत्व" सरणी में पहला तत्व खोजने के लिए कहती है, जो किसी सरणी में वास्तव में k समय होता है। यदि सरणी में कोई ऐसा तत्व नहीं है जो k बार होता है तो -1 लौटाएं।

उदाहरण

किसी श्रेणी के लापता तत्व खोजें

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

व्याख्या

इस उदाहरण में, दो तत्व हैं जो k समय के होते हैं। 4 और 2, वास्तव में k की संख्या के बराबर होते हैं, लेकिन 4 वह पहली बार होता है जो k समय के अनुसार होता है। तो हम 4 लौटाते हैं।

कलन विधि

  1. डिक्लेयर ए हैश मैप.
  2. सरणी को पीछे छोड़ें।
    • सरणी के प्रत्येक तत्व की आवृत्ति को मानचित्र में गिनें और संग्रहीत करें।
  3. फिर से एरे को ट्रेव करें और जांचें कि क्या प्रत्येक एरे तत्व की आवृत्ति k के बराबर है।
    • यदि स्थिति संतुष्ट होती है, तो तत्व वापस करें।

व्याख्या

हमारे पास हमारे इनपुट मान हैं पूर्णांक सरणी और एक पूर्णांक कश्मीर। समस्या कथन एक सरणी में पहले तत्व का पता लगाने के लिए कहता है जो वास्तव में k बार होता है। इस समस्या को हल करने के लिए, हम उपयोग करने जा रहे हैं hashing। हैशिंग संभव तरीका है जिसके द्वारा हम अपनी समय की जटिलता को कम कर सकते हैं। इसकी लागत है पर) समय जटिलता।

हम अपने नक्शे में प्रत्येक तत्व की आवृत्ति को गिनेंगे और संग्रहीत करेंगे। मान लीजिए कि एक तत्व 3 बार आता है एक सरणी में हम उस तत्व के साथ इसकी आवृत्ति 3 के रूप में सेट करते हैं। कुंजी और मान संग्रहीत करने के लिए इस उद्देश्य के लिए HashMap का उपयोग किया जा सकता है। हम सभी तत्वों को कुंजी और उनकी आवृत्तियों के रूप में एक हाशप में मान के रूप में संग्रहीत करेंगे। फिर हम एक लूप चलाएंगे और एक सरणी को पार करेंगे और प्रत्येक तत्व को उठाएंगे और उनकी आवृत्ति की जांच करेंगे। यदि किसी तत्व की आवृत्ति k के बराबर पाई जाती है, तो हम उस तत्व को वापस कर देंगे। चूंकि हम एरे को ट्रेस कर रहे हैं, इसलिए यदि तत्व k के समय के साथ पाया जाता है। फिर निश्चित रूप से यह ऐसा पहला तत्व होगा जिसमें कोई घटना नहीं होगी।

चलिए, हम एक उदाहरण पर विचार करते हैं:

arr [] = {2,4,6,4,2,1,}, k = 2

हम मानचित्र में मान के रूप में तत्वों और उनकी आवृत्तियों के रूप में भंडारण करेंगे, हमारे मानचित्र के भंडारण के बाद निम्नलिखित मान होंगे:

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

हम प्रत्येक सरणी तत्व की जांच करेंगे, 0 वें इंडेक्स से शुरू होकर हम एरे को ट्रेस करना शुरू करेंगे

i = 0,

यदि प्रत्येक सरणी की आवृत्ति [i] == k:

2 की आवृत्ति 2 है, जो कि k के बराबर है, यह वह तत्व है, जो k की किसी भी घटना के साथ आता है, इसलिए हम गिरफ्तारी को वापस करते हैं [i] और हमारा आउटपुट 2 होगा।

यदि किसी तत्व की आवृत्ति 'k' के साथ मेल नहीं खाएगी, तो हम -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

जटिलता विश्लेषण

समय जटिलता

पर) जहां "N" सरणी में तत्वों की संख्या है। यहाँ, चूंकि हमने हैशमैप का उपयोग किया है इसलिए हम ओ (1) समय में ऑपरेशन करने में सक्षम थे।

अंतरिक्ष जटिलता

पर) जहां "N" सरणी में तत्वों की संख्या है। सबसे खराब स्थिति में जब सभी तत्व अलग-अलग होते हैं। हमें सभी N तत्वों को मानचित्र में संग्रहीत करना होगा जो रैखिक स्थान लेंगे।