पहला नॉन रिपीटिंग एलीमेंट  


कठिनाई स्तर आसान
में अक्सर पूछा बेलजब्बर कोमली मीडिया मेटलाइफ स्नैपडील Sprinklr वुकर
ऐरे हैश खोजना

हमें एक सरणी दी जाती है। हमें सरणी में पहला गैर दोहराव वाला तत्व ढूंढना है।

उदाहरण  

इनपुट:

A [] = {2,1,2,1,3,4}

आउटपुट:

पहला गैर-दोहराव तत्व है: 3

क्योंकि 1, 2 उत्तर नहीं है क्योंकि वे दोहरा रहे हैं और 4 उत्तर नहीं है क्योंकि हमें पहला non_repeating तत्व ढूंढना है, जो 3 है, 4 नहीं।

दृष्टिकोण 1: क्रूर बल  

मुख्य विचार

में हर तत्व के लिए सरणी, हम पूरे ऐरे को इट्रैट करेंगे और अगर यह तत्व न दोहरा रहा है तो हम इस तत्व को प्रिंट करेंगे।

कलन विधि

  1. I को 0 से n-1 तक के लिए एक लूप चलाएं
    1. J से 0 से n तक के लिए एक लूप चलाएँ
      1. यदि j n के बराबर हो जाता है, तो A [i] प्रिंट करें और वापस लौटें।
      2. अगर मैं j और A [i] के बराबर नहीं हूँ, तो A [j] के बराबर है, तो इस लूप से विराम लें।
    2. प्रिंट करें कि सभी तत्व सरणी में दोहरा रहे हैं।

पहले गैर दोहराए जाने वाले तत्व के लिए कार्यान्वयन

C ++ प्रोग्राम

#include <bits/stdc++.h>
using namespace std;
void firstNonRepeatingElement(vector<int> &A)
{
    int n = A.size();
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j <= n; j++)
        {
            if (j == n)
            {
                cout << "First non-repeating element is: " << A[i] << endl;
                return;
            }
            if (j != i and A[i] == A[j])
            {
                break;
            }
        }
    }
    cout << "All the elements are repeating." << endl;
}
int main()
{
    vector<int> A = {2, 1, 2, 1, 3, 4};
    firstNonRepeatingElement(A);
    return 0;
}
First non-repeating element is: 3

जावा कार्यक्रम

public class Main
{
    static void firstNonRepeatingElement(int A[])
    {
        int n = A.length;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j <= n; j++)
            {
                if (j == n)
                {
                    System.out.println("First non-repeating element is: "+A[i]);
                    return;
                }
                if (j != i && A[i] == A[j])
                {
                    break;
                }
            }
        }
        System.out.println("All the elements are repeating.");
    }
  public static void main(String[] args) {
    int A[]={2, 1, 2, 1, 3, 4};
    firstNonRepeatingElement(A);
  }
}
First non-repeating element is: 3

पहले गैर दोहराए जाने वाले तत्व के लिए जटिलता विश्लेषण

समय जटिलता

हमारे पास आकार एन के दोनों नेस्टेड छोरों हैं, इसलिए कुल समय जटिलता है ओ (एन ^ 2).

यह भी देखें
एक स्ट्रिंग Leetcode समाधान के उल्टे स्वर

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

हम किसी भी अतिरिक्त स्थान का उपयोग नहीं कर रहे हैं इसलिए अंतरिक्ष जटिलता है ओ (1).

दृष्टिकोण 2: हैशिंग का उपयोग करना  

मुख्य विचार

हम एक हैश तालिका में प्रत्येक तत्व की आवृत्ति को संग्रहीत कर सकते हैं और उसके बाद हम सरणी को पार कर सकते हैं और पहला तत्व ढूंढ सकते हैं जिसकी आवृत्ति 1 है।

कलन विधि

  1. एक हैश तालिका में प्रत्येक तत्व की आवृत्ति को स्टोर करें।
  2. I को 0 से n-1 तक के लिए एक लूप चलाएं
    1. यदि हैश तालिका में A [i] की आवृत्ति 1 है, तो A [i] प्रिंट करें और वापस लौटें।
  3. दोहराएं कि सरणी में सभी तत्व हैं जो दोहरा रहे हैं।

उदाहरण के साथ समझें

ए [] = {२, ३, २, २, ०, ४}

फिर हैश तालिका इस तरह दिखाई देगी:

पहला नॉन रिपीटिंग एलीमेंटपिन

पहले गैर दोहराए जाने वाले तत्व के लिए कार्यान्वयन

C ++ प्रोग्राम

#include <bits/stdc++.h>
using namespace std;
void firstNonRepeatingElement(vector<int> &A)
{
    int n = A.size();
    unordered_map<int, int> hash_table;
    for (int i = 0; i < n; i++)
    {
        hash_table[A[i]]++;
    }
    for (int i = 0; i < n; i++)
    {
        if (hash_table[A[i]] == 1)
        {
            cout << "First non-repeating element is: " << A[i] << endl;
            return;
        }
    }
    cout << "All the elements are repeating." << endl;
}
int main()
{
    vector<int> A = {2, 1, 2, 1, 3, 4};
    firstNonRepeatingElement(A);
    return 0;
}
First non-repeating element is: 3

जावा कार्यक्रम

public class Main
{
    static void firstNonRepeatingElement(int A[])
    {
        java.util.HashMap<Integer, Integer> hash_table = new java.util.HashMap<Integer, Integer>();
        int n = A.length;
        for(int i=0;i<n;i++)
        {
            Integer freq = hash_table.get(A[i]);
            hash_table.put(A[i], (freq == null) ? 1 : freq + 1); 
        }

        for (int i = 0; i < n; i++)
        {
            if (hash_table.get(A[i])==1)
            {
                System.out.println("First non-repeating element is: "+A[i]);
                return;
            }
        }
        System.out.println("All the elements are repeating.");
    }
  public static void main(String[] args) {
    int A[]={2, 1, 2, 1, 3, 4};
    firstNonRepeatingElement(A);
  }
}
First non-repeating element is: 3

पहले गैर दोहराए जाने वाले तत्व के लिए जटिलता विश्लेषण

समय जटिलता

हम सरणी को केवल दो बार पुनरावृत्त कर रहे हैं ताकि कुल समय जटिलता हो पर).

यह भी देखें
आकार k के सभी उपग्रहों के न्यूनतम और अधिकतम तत्वों का योग

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

हम एक हैश तालिका बनाए रख रहे हैं ताकि अंतरिक्ष की जटिलता हो पर).

संदर्भ