एर्रे लेटकोड समाधानमा गायब सबै नम्बरहरू फेला पार्नुहोस्


कठिनाई तह सजिलो
बारम्बार सोधिन्छ एडोब अमेजन एप्पल ब्लूमबर्ग गुगल माइक्रोसफ्ट याहू
एरे ह्याशिंग

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

यस समस्यामा, हामीलाई एक दिइन्छ array पूर्णांकको। यसले १ देखि N सम्म एलिमेन्टहरू समावेश गर्दछ, जहाँ N = आकार एर्रेको। यद्यपि त्यहाँ केहि तत्वहरू छन् जुन हराइसकेका छन् र केहि नक्कल उनीहरूको ठाउँमा उपस्थित छन्। हाम्रो लक्ष्य त्यस्ता सबै हराएको पूर्णांकहरूको एरे फिर्ता गर्नु हो।

उदाहरणका

Array = {1 , 2 , 5 , 6 , 2 , 5}
3 4

एर्रे लेटकोड समाधानमा गायब सबै नम्बरहरू फेला पार्नुहोस्

Array = {1 , 2 , 3 , 4}
n

एर्रे लेटकोड समाधानमा गायब सबै नम्बरहरू फेला पार्नुहोस्

दृष्टिकोण (ह्याशसेट प्रयोग गर्दै)

हामी एर्रेमा प्रत्येक तत्व मार्क गर्न सक्छौं र दायरा भित्र लूप: [१, N] कुन एरमेन्ट हरायो वा एर्रेमा हराइरहेको छ भनेर जाँच गर्न। हामी भण्डार गर्न ह्यास सेट प्रयोग गर्छौं कि पूर्णांक अंकित गरिएको छ वा छैन।

अल्गोरिदम

  1. ह्याश सेट सुरु गर्नुहोस् चिन्ह लगाउनुहोस् [पूर्णांक] उपस्थित तत्वहरू भण्डार गर्न।
  2. प्रत्येक तत्वका लागि i एर्रेमा:
    • थप i लाई मार्क
  3. एक सूची / भेक्टर सुरु गर्नुहोस् परिणाम एर्रेमा हराएको तत्वहरू भण्डार गर्न
  4. प्रत्येक तत्वका लागि दायरामा: [१, N]:
    • If मा उपस्थित छैन चिन्ह:
      • यसलाई जोड्नुहोस् परिणाम
  5. फिर्ती परिणाम
  6. परिणाम प्रिन्ट गर्नुहोस्

एरे लेटकोड समाधानमा गायब सबै नम्बरहरू फेला पारेर कार्यान्वयन

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

#include <bits/stdc++.h>
using namespace std;

vector <int> findDisappearedNumbers(vector <int> &a)
{
    unordered_set <int> mark;
    for(int &i : a)
        mark.insert(i);
    int N = a.size();
    vector <int> result;
    for(int i = 1 ; i <= N ; i++)
        if(mark.find(i) == mark.end())
            result.emplace_back(i);

    return result;
}

int main()
{
    vector <int> a = {1 , 2 , 5 , 6 , 2 , 5};
    vector <int> result = findDisappearedNumbers(a);
    if(result.empty())
        cout << "No disappeared elements\n";
    else
        for(int &i : result)
            cout << i << " ";
    return 0;
}

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

import java.util.*;

class find_disappeared_numbers
{
    public static void main(String args[])
    {
        int[] a = {1 , 2 , 5 , 6 , 2 , 5};
        List <Integer> result = findDisappearedNumbers(a);
        if(result.size() == 0)
            System.out.println("No disappeared elements");
        else
            for(int i : result)
                System.out.print(i + " ");
    }

    static List <Integer> findDisappearedNumbers(int[] a)
    {
        List <Integer> result = new ArrayList <Integer>();
        HashSet <Integer> mark = new HashSet <Integer>();
        for(int i : a)
            mark.add(i);

        for(int i = 1 ; i <= a.length ; i++)
            if(!mark.contains(i))
                result.add(i);

        return result;
    }
}
3 4

एरे लेटकोड समाधानमा गायब सबै नम्बरहरू भेट्टाउने जटिलता विश्लेषण

समय जटिलता

O (N) जस्तो कि हामीले पूर्णाray्कहरू मार्क गर्न एर्रे लाई एक पटक ट्र्याभर्स गर्छौं। N = एर्रेको आकार।

ठाउँ जटिलता 

O (N) किनकि हामी ह्यास तालिकामा एर्रेमा उपस्थित सबै नम्बरहरू भण्डार गर्छौं। नोट गर्नुहोस् कि हामी अन्तरिक्ष जटिलता योगदानमा आउटपुट एर्रेलाई विचार गर्दैनौं।

दृष्टिकोण (स्थान मा संशोधन)

यस समस्यामा ध्यान दिन एउटा बुँदा यो हो: "एर्रेमा तत्वहरू समावेश हुन्छन यसको आकार भन्दा कम वा बराबर"। यसको मतलव त्यहाँ धेरै सूचकहरु धेरै फरक तत्वहरू छन्। साथै, हराइरहेको तत्त्वहरू सँधै N (एरेको आकार) भन्दा कम हुन्छन्। यो अवरोधको प्रयोग गरेर, हामी एर्रेको प्रयोग गर्न सक्दछौं कुनै प्रकार पूर्णाger्कको उपस्थिति भण्डारण गर्न। उदाहरण को लागी, मानौं हामी लेख्न सक्छौं सही / गलत एलिमेन्टको सूचकांकमा क्रमशः यसको उपस्थिति / अनुपस्थितिलाई दर्शाउन। हाम्रो केसमा एरेमा पहिले नै एलिमेन्टहरू छन्, त्यसैले यस प्रकारको भण्डारण / मेमोइजेसन सम्भव छैन। जे होस्, हामीलाई थाहा छ कि सबै तत्वहरू सकारात्मक छन्, हामी एरेमा एलिमेन्ट देखेका छौं कि छैन भनेर संकेतको रूपमा "नकारात्मक" प्रयोग गर्न सक्छौं। नोट गर्नुहोस् कि हामी प्रयोग गरेर केहि सूचकांकमा भण्डार गरिएको वास्तविक मूल्य ल्याउन सक्छौं निरपेक्ष () प्रकार्य जसले पूर्णांकको पूर्ण मान फिर्ता गर्छ। यस तरिकाले एरे दुबै ह्यास नक्शा र कन्टेनरको रूपमा प्रयोग गर्न सकिन्छ।

उदाहरणको लागि, यदि हामीले एर्रेमा एलिमेन्ट '२' देख्यौं भने हामी एर्रेलाई एरई [१] = -१ * एरे [१] प्रदान गर्न सक्दछौं जसले हामीलाई एलिमेन्ट २ एरेमा देखापर्छ भनेर बताउँछ।

यो ट्रिकले स्थानमा एर्रे स्थानमा हेरफेर गर्दछ यदि हामीले सूचकांकमा एक एलिमेन्ट देख्यौं i। एकपटक सकिएपछि, हामी दायरा [१, N] मा एउटा लूप चलाउन सक्दछौं गैर इन्टिग्रेट भएका सबै इन्टेजरहरू (जुन उनीहरूले देखेका छैनन) फेला पार्न र यसको लागि आवश्यक परिणाम प्रिन्ट गर्नुहोस्। नोट गर्नुहोस् कि यो मात्र सम्भव छ यदि हामी छौं अनुमति दिइयो एर्रे परिवर्तन गर्न

अल्गोरिदम

  1. प्रत्येक तत्वका लागि एर्रेमा:
    • यदि एर्रे [i - 1]> ०:
      • यसलाई नकारात्मक, वा, एर्रेको रूपमा सेट गर्नुहोस् [i - 1] * = -1;
  2. एक सूची / भेक्टर सुरु गर्नुहोस् परिणाम सबै हराइरहेको तत्व भण्डारण गर्न
  3. प्रत्येक पूर्णांकको लागि दायरा [१, N] मा (N = एर्रेको आकार):
    • If एर्रे [i]> ०
      • यो तत्व थप्नुहोस् i लाई परिणाम
  4. फिर्ती परिणाम
  5. परिणाम प्रिन्ट गर्नुहोस्

एरे लेटकोड समाधानमा गायब सबै नम्बरहरू फेला पारेर कार्यान्वयन

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

#include <bits/stdc++.h>
using namespace std;

vector <int> findDisappearedNumbers(vector <int> &a)
{
    int N = a.size();
    int idx;
    for(int i = 0 ; i < N ; i++)
    {
        idx = abs(a[i]) - 1;
        if(a[idx] > 0)
            a[idx] *= -1;
    }

    vector <int> result;
    for(int i = 0 ; i < N ; i++)
        if(a[i] > 0)
            result.emplace_back(i + 1);

    return result;
}

int main()
{
    vector <int> a = {1 , 2 , 5 , 6 , 2 , 5};
    vector <int> result = findDisappearedNumbers(a);
    if(result.empty())
        cout << "No disappeared elements\n";
    else
        for(int &i : result)
            cout << i << " ";
    return 0;
}

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

import java.util.*;
import java.lang.Math;

class find_disappeared_numbers
{
    public static void main(String args[])
    {
        int[] a = {1 , 2 , 5 , 6 , 2 , 5};
        List <Integer> result = findDisappearedNumbers(a);
        if(result.size() == 0)
            System.out.println("No disappeared elements");
        else
            for(int i : result)
                System.out.print(i + " ");
    }

    static List <Integer> findDisappearedNumbers(int[] a)
    {
        int idx;
        for(int i = 0 ; i < a.length ; i++)
        {
            idx = Math.abs(a[i]) - 1;
            if(a[idx] > 0)
                a[idx] *= -1;
        }

        List <Integer> result = new ArrayList <Integer> ();

        for(int i = 0 ; i < a.length ; i++)
            if(a[i] > 0)
                result.add(i + 1);

        return result;
    }
}
3 4

एरे लेटकोड समाधानमा गायब सबै नम्बरहरू भेट्टाउने जटिलता विश्लेषण

समय जटिलता

O (N) किनकि हामी हराइरहेका तत्वहरू फेला पार्न इनपुटको पर्वाह नगरी एर्रेको दुई पासहरू चलाउँछौं। N = एर्रेको आकार।

ठाउँ जटिलता 

O (१) जस्तो कि हामी स्थिर मेमोरी स्पेस प्रयोग गर्छौं।