ഒരു അറേ ലീറ്റ്കോഡ് പരിഹാരത്തിൽ അപ്രത്യക്ഷമായ എല്ലാ നമ്പറുകളും കണ്ടെത്തുക


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു അഡോബി ആമസോൺ ആപ്പിൾ ബ്ലൂംബർഗ് ഗൂഗിൾ മൈക്രോസോഫ്റ്റ് യാഹൂ
അറേ ഹാഷിംഗ്

ഉള്ളടക്ക പട്ടിക

പ്രശ്നം പ്രസ്താവന

ഈ പ്രശ്‌നത്തിൽ, ഞങ്ങൾക്ക് ഒരു നൽകിയിട്ടുണ്ട് ശ്രേണി പൂർണ്ണസംഖ്യകളുടെ. ഇതിൽ 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

ഒരു അറേ ലീറ്റ്കോഡ് പരിഹാരത്തിൽ അപ്രത്യക്ഷമായ എല്ലാ നമ്പറുകളും കണ്ടെത്തുന്നതിന്റെ സങ്കീർണ്ണ വിശകലനം

സമയ സങ്കീർണ്ണത

O (N) പൂർണ്ണസംഖ്യകൾ അടയാളപ്പെടുത്തുന്നതിന് ഞങ്ങൾ മുഴുവൻ അറേയും ഒരു തവണ സഞ്ചരിക്കുമ്പോൾ. N = അറേയുടെ വലുപ്പം.

ബഹിരാകാശ സങ്കീർണ്ണത 

O (N) അറേയിലുള്ള എല്ലാ അക്കങ്ങളും ഞങ്ങൾ ഒരു ഹാഷ് പട്ടികയിൽ സംഭരിക്കുന്നതിനാൽ. ബഹിരാകാശ സങ്കീർണ്ണത സംഭാവനയിലെ array ട്ട്‌പുട്ട് അറേ ഞങ്ങൾ പരിഗണിക്കുന്നില്ലെന്നത് ശ്രദ്ധിക്കുക.

സമീപനം (സ്ഥലത്തെ പരിഷ്‌ക്കരണം)

ഈ പ്രശ്‌നത്തിൽ ശ്രദ്ധിക്കേണ്ട ഒരു കാര്യം ഇതാണ്: “അറേയിൽ എല്ലായ്പ്പോഴും അതിന്റെ വലുപ്പത്തേക്കാൾ കുറവോ തുല്യമോ ആയ ഘടകങ്ങൾ അടങ്ങിയിരിക്കുന്നു”. ഇതിനർത്ഥം വ്യത്യസ്ത ഘടകങ്ങളുടെ അത്രയും സൂചികകളുണ്ട്. കൂടാതെ, കാണാത്ത ഘടകങ്ങൾ എല്ലായ്പ്പോഴും 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

ഒരു അറേ ലീറ്റ്കോഡ് പരിഹാരത്തിൽ അപ്രത്യക്ഷമായ എല്ലാ നമ്പറുകളും കണ്ടെത്തുന്നതിന്റെ സങ്കീർണ്ണ വിശകലനം

സമയ സങ്കീർണ്ണത

O (N) നഷ്‌ടമായ ഘടകങ്ങൾ കണ്ടെത്തുന്നതിന് ഇൻപുട്ട് പരിഗണിക്കാതെ തന്നെ ഞങ്ങൾ അറേയുടെ രണ്ട് പാസുകൾ പ്രവർത്തിപ്പിക്കുമ്പോൾ. N = അറേയുടെ വലുപ്പം.

ബഹിരാകാശ സങ്കീർണ്ണത 

O (1) ഞങ്ങൾ സ്ഥിരമായ മെമ്മറി ഇടം ഉപയോഗിക്കുന്നതിനാൽ.