दिइएको एर्रेमा पहिलो दोहोर्याउने नम्बर फेला पार्नुहोस्  


कठिनाई तह सजिलो
बारम्बार सोधिन्छ एडोब अमेजन एप्पल ब्लूमबर्ग Citadel eBay फेसबुक Goldman सैक्स गुगल Intuit माइक्रोसफ्ट नुटानिक्स बजेट PayPal SalesForce इच्छा याहू
एरे हैश खोजी Zynga

समस्या वक्तव्य  

त्यहाँ धेरै दोहोर्याउने नम्बरहरू हुन सक्छन् array तर तपाईंले दिइएको एर्रेमा पहिलो दोहोर्याउने नम्बर फेला पार्नु पर्छ (दोस्रो पटक हुने)।

उदाहरणका  

आगत

12

5 4 2 8 9 7 12 5 6 12 4 7

उत्पादन

The पहिलो दोहोरिने तत्त्व हो

पहिलो दोहोर्याउने नम्बर खोज्नुहोस्  

साधारणतया हामी ह्याशिंग प्रयोग गर्न सक्दछौं जहाँ हामी एर्रेको एलिमेन्ट्सको मान राख्छौं र घटनाको गन्ती बढाउँदै। जति सक्दो हामी गनति १ को साथ एक एलिमेन्ट पाउँदछौं अर्थात् जुन पहिले नै भएको छ हामी पहिलो दोहोर्‍याउने एलिमेन्ट पाउँछौं।

अल्गोरिदम

१ एर्रेको प्रत्येक एलिमेन्ट ट्रान्सवर्स गर्नुहोस्।

२. प्रत्येक तत्वको फ्रिक्वेन्सी बढाउनुहोस्।

Any. यदि कुनै पनि तत्त्व जसको आवृत्ति १ भन्दा बढी छ भने सिधा सिधा प्रिन्ट गर्नुहोस्।

कार्यान्वयन

C ++ कार्यक्रम

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

import java.util.HashMap;
import java.util.Scanner;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        HashMap <Integer,Integer> m = new HashMap<Integer, Integer>();
        int ans=0;
        for(int i=0;i<n;i++)
        {
            int x = m.get(a[i])==null ? 1: m.get(a[i])+1;
            m.put(a[i], x);
            if(m.get(a[i])>1)
            {
                ans=a[i];
                break;
            }
        }
        if(ans==0)
        {
            System.out.println("No element repeated");
        }
        else
        {
          System.out.println(ans);
        }
    }
}
12
5 4 2 8 9 7 12 5 6 12 4 7
5

पहिलो दोहोरिएको संख्या फेला पार्ने जटिलता विश्लेषण

समय जटिलता- O (N) जहाँ एन एरेको आकार हो। यहाँ हामी एरेमा पुनरावृत्ति गर्छौं र ह्याश म्यापमा एलिमेन्ट्सको फ्रिक्वेन्सी / गणना भण्डार गर्दछौं।

पनि हेर्नुहोस्
एर्रे पालिन्ड्रोम बनाउन मर्ज अपरेशनहरूको न्यूनतम संख्या फेला पार्नुहोस्

अन्तरिक्ष जटिलता - O (N) किनभने हामी फ्रिक्वेन्सी ओ एलिमेन्ट र ह्यास नक्शाको अधिकतम आकार गणना गर्दछ O (n)।

दृष्टिकोण दोहोर्याउनुहोस् पहिलो दोहोर्याउने नम्बर खोज्नुहोस्  

यहाँ हामी नक्सा प्रयोग गर्छौं जसले एर्रेमा एलिमेन्ट उपस्थित हुन एब्स र न राख्दछ। यदि तत्व छ भने यो समावेश गर्दछ साँचो मानचित्र मा कि तत्व को सम्मान को साथ। यदि तत्व उपस्थित छैन भने यसलाई कायम गर्दछ झूटा मानचित्र मा कि तत्व को सम्मान को साथ।

अल्गोरिदम

१. एर्रे एलिमेन्टको मानलाई कुञ्जी बनाएर कुञ्जी-मान जोडीको रूपमा गणना गर्नुहोस्।

२ को गणनाको साथ जोडी १ को रूपमा शुरू गर्नुहोस् र यसलाई वृद्धि गर्नुहोस्।

Soon. जति सक्दो हामी एउटा एलिमेन्ट पाउँदछौं जसको गन्ती १ छ हामी पहिलो दोहोरिने तत्त्व पाउँछौं

कार्यान्वयन

C ++ कार्यक्रम

#include <bits/stdc++.h>
using namespace std;
int main()
{
  
  int n;
  cin>>n;
  int arr[n];
  for(int i=0;i<n;i++)
  {
      cin>>arr[i];
  }
  map <int,bool> M; // create a map with key as the array element and value as if it is present or not
  map <int,bool> :: iterator it;
  for(int i=0;i<n;i++)
    {
      it = M.find(arr[i]); //find the array element in map
      if(it != M.end()) // if present then it is the first element to be repeated
        {
          cout<<arr[i] <<endl;
          return 0;
        }
      else
        M.insert(make_pair(arr[i],true)); //else insert it into the map setting the value as true
    }
  cout<<"No element repeated"<<endl;
  return 0;
  
}

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

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        Map <Integer,Integer> m = new HashMap<Integer, Integer>() {}; // create a map with key as the array element and value as if it is present or not
        int frank=0;
        for(int i=0;i<n;i++)
        {
            boolean temp = m.containsValue(a[i]);
            if(temp) // if present then it is the first element to be repeated
            {
                System.out.println(a[i]);
                frank=1;
                i=n;
            }
            else
            {
               m.put(a[i],1); //else insert it into the map setting the value as true
            }
          }
        if(frank==0)
        System.out.println("No element repeated");
    }
}
6
1 2 3 4 5 6
No element repeated

पहिलो दोहोरिएको संख्या फेला पार्ने जटिलता विश्लेषण

समय जटिलता - O (NlogN) किनकि नक्शामा सम्मिलनले O (लगइन) समय लिन्छ र हामी यहाँ नक्सामा n तत्व घुसाउँछौं।

पनि हेर्नुहोस्
एक सबभरिमा भिन्न तत्वहरूको संख्याको लागि प्रश्नहरू

अन्तरिक्ष जटिलता - O (N) किनभने हामी नक्शा प्रयोग गर्दछौं कि त्यो तत्व छैन मा उपस्थित छ।

सन्दर्भ