శ్రేణి లీట్‌కోడ్ పరిష్కారంలో కనిపించని అన్ని సంఖ్యలను కనుగొనండి


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది Adobe అమెజాన్ ఆపిల్ బ్లూమ్బెర్గ్ గూగుల్ మైక్రోసాఫ్ట్ యాహూ
అర్రే హ్యాషింగ్

విషయ సూచిక

సమస్యల నివేదిక

ఈ సమస్యలో, మాకు ఒక ఇవ్వబడుతుంది అమరిక పూర్ణాంకాల. ఇది 1 నుండి N వరకు మూలకాలను కలిగి ఉంటుంది, ఇక్కడ శ్రేణి యొక్క N = పరిమాణం. అయినప్పటికీ, కొన్ని అంశాలు అదృశ్యమయ్యాయి మరియు వాటి స్థానంలో కొన్ని నకిలీలు ఉన్నాయి. అదృశ్యమైన పూర్ణాంకాల శ్రేణిని తిరిగి ఇవ్వడమే మా లక్ష్యం.

ఉదాహరణ

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

శ్రేణి లీట్‌కోడ్ పరిష్కారంలో కనిపించని అన్ని సంఖ్యలను కనుగొనండి

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

శ్రేణి లీట్‌కోడ్ పరిష్కారంలో కనిపించని అన్ని సంఖ్యలను కనుగొనండి

అప్రోచ్ (హాష్‌సెట్ ఉపయోగించి)

మేము శ్రేణిలోని ప్రతి మూలకాన్ని గుర్తించి, ఆపై పరిధిలో లూప్ చేయవచ్చు: [1, N] ఏ అంశాలు అదృశ్యమయ్యాయో లేదా శ్రేణిలో తప్పిపోయాయో తనిఖీ చేయడానికి. పూర్ణాంకం గుర్తించబడిందా లేదా అనే విషయాన్ని నిల్వ చేయడానికి మేము హాష్ సెట్‌ను ఉపయోగిస్తాము.

అల్గారిథం

  1. హాష్ సెట్‌ను ప్రారంభించండి గుర్తు [పూర్ణాంకం] ఉన్న అంశాలను నిల్వ చేయడానికి.
  2. ప్రతి మూలకం కోసం i శ్రేణిలో:
    • చేర్చు i కు మార్క్
  3. జాబితా / వెక్టర్ ప్రారంభించండి ఫలితంగా శ్రేణిలో తప్పిపోయిన అంశాలను నిల్వ చేయడానికి
  4. ప్రతి మూలకం కోసం పరిధిలో: [1, N]:
    • If లో లేదు గుర్తు:
      • దీనికి జోడించండి ఫలితంగా
  5. రిటర్న్ ఫలితంగా
  6. ఫలితాన్ని ముద్రించండి

శ్రేణి లీట్‌కోడ్ పరిష్కారంలో కనిపించని అన్ని సంఖ్యలను కనుగొనడం అమలు

సి ++ ప్రోగ్రామ్

#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

శ్రేణి లీట్‌కోడ్ పరిష్కారంలో కనిపించని అన్ని సంఖ్యలను కనుగొనడం యొక్క సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

పై) పూర్ణాంకాలను గుర్తించడానికి మేము మొత్తం శ్రేణిని ఒకసారి ప్రయాణిస్తున్నప్పుడు. N = శ్రేణి యొక్క పరిమాణం.

అంతరిక్ష సంక్లిష్టత 

పై) మేము శ్రేణిలో ఉన్న అన్ని సంఖ్యలను హాష్ పట్టికలో నిల్వ చేస్తున్నప్పుడు. స్పేస్ సంక్లిష్టత సహకారంలో అవుట్పుట్ శ్రేణిని మేము పరిగణించలేదని గమనించండి.

అప్రోచ్ (స్థలంలో మార్పు)

ఈ సమస్యలో గమనించవలసిన ఒక విషయం ఏమిటంటే: “శ్రేణి ఎల్లప్పుడూ దాని పరిమాణానికి తక్కువ లేదా సమానమైన అంశాలను కలిగి ఉంటుంది”. దీని అర్థం అనేక విభిన్న అంశాలు ఉన్నంత ఎక్కువ సూచికలు ఉన్నాయి. అలాగే, తప్పిపోయిన అంశాలు ఎల్లప్పుడూ N (శ్రేణి పరిమాణం) కంటే తక్కువగా ఉంటాయి. ఈ అడ్డంకిని ఉపయోగించి, ఒక పూర్ణాంకం యొక్క ఉనికిని ఏదో ఒక విధంగా నిల్వ చేయడానికి మేము శ్రేణిని ఉపయోగించవచ్చు. ఉదాహరణకు, మేము వ్రాయగలమని అనుకోండి ఒప్పు తప్పు మూలకం యొక్క సూచిక వద్ద వరుసగా దాని ఉనికి / లేకపోవడాన్ని సూచిస్తుంది. మా విషయంలో, శ్రేణి ఇప్పటికే అంశాలను కలిగి ఉంది, కాబట్టి ఈ రకమైన నిల్వ / జ్ఞాపకం సాధ్యమయ్యేలా లేదు. అయినప్పటికీ, అన్ని అంశాలు సానుకూలంగా ఉన్నాయని మనకు తెలుసు కాబట్టి, మనం శ్రేణిలో ఒక మూలకాన్ని చూశారా లేదా అనే విషయాన్ని సూచించే చిహ్నంగా “నెగటివ్” ను ఉపయోగించవచ్చు. మేము కొన్ని సూచిక వద్ద నిల్వ చేసిన వాస్తవ విలువను ఉపయోగించడం ద్వారా పొందగలమని గమనించండి సంపూర్ణ() పూర్ణాంకం యొక్క సంపూర్ణ విలువను తిరిగి ఇచ్చే ఫంక్షన్. ఈ విధంగా, శ్రేణిని హాష్ మ్యాప్ మరియు కంటైనర్‌గా ఉపయోగించవచ్చు.

ఉదాహరణకు, మేము శ్రేణిలో '2' మూలకాన్ని చూసినట్లయితే, మేము అర్రే [1] = -1 * అర్రే [1] ను కేటాయించవచ్చు, ఇది శ్రేణి 2 లో మూలకం కనిపిస్తుంది అని మాకు తెలియజేస్తుంది.

ఈ ట్రిక్ మేము ఇండెక్స్ వద్ద ఒక మూలకాన్ని చూసినట్లయితే నిల్వ చేయడానికి స్థలంలో శ్రేణిని మారుస్తుంది i. పూర్తి చేసిన తర్వాత, ప్రతికూలత లేని అన్ని పూర్ణాంకాలను కనుగొనడానికి [1, N] పరిధిలో లూప్‌ను అమలు చేయవచ్చు (అంటే అవి చూడలేదని అర్థం) మరియు అందువల్ల, అవసరమైన ఫలితాన్ని ప్రింట్ చేయండి. మనం ఉంటేనే ఇది సాధ్యమవుతుందని గమనించండి అనుమతి శ్రేణిని మార్చడానికి.

అల్గారిథం

  1. ప్రతి మూలకం కోసం శ్రేణిలో:
    • అర్రే ఉంటే [i - 1]> 0:
      • దీన్ని ప్రతికూలంగా సెట్ చేయండి లేదా, అర్రే [i - 1] * = -1;
  2. జాబితా / వెక్టర్ ప్రారంభించండి ఫలితంగా తప్పిపోయిన అన్ని అంశాలను నిల్వ చేయడానికి
  3. ప్రతి పూర్ణాంకానికి [1, N] పరిధిలో (శ్రేణి యొక్క N = పరిమాణం):
    • If శ్రేణి [i]> 0
      • ఈ మూలకాన్ని జోడించండి i కు ఫలితంగా
  4. రిటర్న్ ఫలితంగా
  5. ఫలితాన్ని ముద్రించండి

శ్రేణి లీట్‌కోడ్ పరిష్కారంలో కనిపించని అన్ని సంఖ్యలను కనుగొనడం అమలు

సి ++ ప్రోగ్రామ్

#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

శ్రేణి లీట్‌కోడ్ పరిష్కారంలో కనిపించని అన్ని సంఖ్యలను కనుగొనడం యొక్క సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

పై) తప్పిపోయిన అంశాలను కనుగొనడానికి ఇన్‌పుట్‌తో సంబంధం లేకుండా మేము శ్రేణి యొక్క రెండు పాస్‌లను నడుపుతున్నప్పుడు. N = శ్రేణి యొక్క పరిమాణం.

అంతరిక్ష సంక్లిష్టత 

O (1) మేము స్థిరమైన మెమరీ స్థలాన్ని ఉపయోగిస్తున్నప్పుడు.