एक ऐरे लेटकोड सॉल्यूशन में गायब हुए सभी नंबर का पता लगाएं


कठिनाई स्तर आसान
में अक्सर पूछा एडोब वीरांगना सेब ब्लूमबर्ग गूगल माइक्रोसॉफ्ट याहू
ऐरे hashing

समस्या का विवरण

इस समस्या में, हमें एक दिया जाता है सरणी पूर्णांकों की। इसमें 1 से एन तक के तत्व शामिल हैं, जहां सरणी का एन = आकार। हालांकि, कुछ तत्व हैं जो गायब हो गए हैं और कुछ डुप्लिकेट उनकी जगह पर मौजूद हैं। हमारा लक्ष्य ऐसे सभी गायब पूर्णांक की एक सरणी को वापस करना है।

उदाहरण

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

एक ऐरे लेटकोड सॉल्यूशन में गायब हुए सभी नंबर का पता लगाएं

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

एक ऐरे लेटकोड सॉल्यूशन में गायब हुए सभी नंबर का पता लगाएं

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

हम सरणी में प्रत्येक तत्व को चिह्नित कर सकते हैं और फिर रेंज में लूप कर सकते हैं: [1, N] यह जांचने के लिए कि कौन से तत्व गायब हो गए हैं या सरणी में गायब हैं। हम यह निर्धारित करने के लिए हैश का उपयोग करते हैं कि कोई पूर्णांक चिह्नित किया गया है या नहीं।

कलन विधि

  1. हैश सेट शुरू करें निशान [पूर्णांक] मौजूद तत्वों को संग्रहीत करने के लिए।
  2. हर तत्व के लिए i सरणी में:
    • जोड़ना i सेवा मेरे निशान
  3. सूची / वेक्टर को आरम्भ करें परिणाम सरणी में लापता तत्वों को संग्रहीत करने के लिए
  4. हर तत्व के लिए रेंज में: [१, एन]:
    • 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

एक Array Leetcode Solution में गायब सभी संख्याओं की जटिलता का विश्लेषण

समय जटिलता

पर) जब हम पूर्णांक को चिह्नित करने के लिए एक बार पूरे सरणी को पार करते हैं। N = सरणी का आकार।

अंतरिक्ष जटिलता 

पर) जैसा कि हम हैश तालिका में सरणी में मौजूद सभी संख्याओं को संग्रहीत करते हैं। ध्यान दें कि हम अंतरिक्ष जटिलता योगदान में आउटपुट सरणी पर विचार नहीं करते हैं।

दृष्टिकोण (इन-प्लेस संशोधन)

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

उदाहरण के लिए, यदि हमने सरणी में एक तत्व '2' देखा है, तो हम Array [1] = -1 * Array [1] निर्दिष्ट कर सकते हैं, जो हमें बताएगा कि तत्व 2 सरणी में देखा गया है।

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

कलन विधि

  1. हर तत्व के लिए सरणी में:
    • अगर एरे [i - 1]> 0:
      • इसे नकारात्मक के रूप में सेट करें, या, ऐरे [i - 1] * = -1;
  2. सूची / वेक्टर को आरम्भ करें परिणाम सभी लापता तत्वों को संग्रहीत करने के लिए
  3. हर पूर्णांक के लिए रेंज में [1, 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

एक Array Leetcode Solution में गायब सभी संख्याओं की जटिलता का विश्लेषण

समय जटिलता

पर) चूंकि हम लापता तत्वों को खोजने के लिए इनपुट के बावजूद सरणी के दो पास चलाते हैं। N = सरणी का आकार।

अंतरिक्ष जटिलता 

ओ (1) जैसा कि हम निरंतर मेमोरी स्पेस का उपयोग करते हैं।