ਐਰੇ ਲੀਟਕੋਡ ਸਲਿ .ਸ਼ਨ ਵਿੱਚ ਅਲੋਪ ਹੋਏ ਸਾਰੇ ਨੰਬਰ ਲੱਭੋ


ਮੁਸ਼ਕਲ ਪੱਧਰ ਸੌਖੀ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਅਡੋਬ ਐਮਾਜ਼ਾਨ ਸੇਬ ਬਲੂਮਬਰਗ ਗੂਗਲ Microsoft ਦੇ ਯਾਹੂ
ਅਰੇ ਹੈਸ਼ਿੰਗ

ਸਮੱਸਿਆ ਦਾ ਬਿਆਨ

ਇਸ ਸਮੱਸਿਆ ਵਿੱਚ, ਸਾਨੂੰ ਇੱਕ ਦਿੱਤਾ ਜਾਂਦਾ ਹੈ ਐਰੇ ਪੂਰਨ ਅੰਕ ਦਾ. ਇਸ ਵਿੱਚ 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 ਐਰੇ ਦਾ ਆਕਾਰ.

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ 

ਓ (1) ਜਿਵੇਂ ਕਿ ਅਸੀਂ ਨਿਰੰਤਰ ਮੈਮੋਰੀ ਸਪੇਸ ਦੀ ਵਰਤੋਂ ਕਰਦੇ ਹਾਂ.