प्रथम अ‍ॅरेमध्ये आणि दुसर्‍या क्रमांकावर नसलेले घटक शोधा


अडचण पातळी सोपे
वारंवार विचारले एकत्रित दिल्लीवारी फॅक्टसेट कट्टरता Snapdeal Zoho
अरे हॅश

“प्रथम अ‍ॅरेमध्ये अस्तित्त्वात असलेले घटक आणि दुसर्‍या क्रमांकावर नसलेले घटक शोधा” ही समस्या सांगते की आपल्याला दोन दिले आहेत अ‍ॅरे. अ‍ॅरेमध्ये सर्व असतात पूर्णांक. आपल्याला दुसर्‍या अ‍ॅरेमध्ये नसतील परंतु पहिल्या अ‍ॅरेमध्ये उपस्थित राहतील असे नंबर शोधावे लागतील.

उदाहरण

प्रथम अ‍ॅरेमध्ये आणि दुसर्‍या क्रमांकावर नसलेले घटक शोधा

a [] = {2,4,3,1,5,6}
b [] = {2,1,5,6}
4 3
a [] ={4,2,6,8,9,5}
b [] ={9,3,2,6,8}
4

अल्गोरिदम

  1. घोषित ए हॅशसेट.
  2. अ‍ॅश बी [] चे सर्व घटक हॅशसेटमध्ये घाला.
  3. मी <l1 (अ‍ॅरेची लांबी a []) असताना.
    1. हॅशसेटमध्ये अ‍ॅरे नसल्यास [i], नंतर एक मुद्रित करा [i].

स्पष्टीकरण

आम्ही दोन पूर्णांक अ‍ॅरे आणि एक समस्या विधान दिले आहे जे पहिल्या अ‍ॅरेमध्ये आहे आणि दुसर्‍या अ‍ॅरेमध्ये नसलेली संख्या शोधण्यासाठी विचारते. आम्ही वापरणार आहोत हॅशिंग या समस्येमध्ये हॅशिंग कार्यक्षम मार्गाने तोडगा शोधण्यात आम्हाला मदत करते.

आपण हॅशसेटमध्ये अ‍ॅरे बी [] संख्या टाकणार आहोत आणि अ‍ॅरे बीची सर्व संख्या समाविष्ट केल्यानंतर. आम्ही अ‍ॅरे अ‍ॅव्हरेज करणार आहोत [आणि प्रत्येक घटक एका वेळी घेत आहोत आणि हॅशसेटमध्ये तो घटक नसल्याचे तपासा. जर त्यास तो घटक नसेल तर आपण अ‍ॅरे एचा विशिष्ट घटक प्रिंट करू आणि [i] आणि दुसर्‍या क्रमांकाची तपासणी करणार आहोत.

चला त्याचं उदाहरण घेऊ आणि हे समजू:

प्रथम अ‍ॅरे एक [] = एक [] = {2,6,8,9,5,4}, बी [] = {9,5,2,6,8} आहे

आपल्याला अ‍ॅरे बी चे सर्व घटक हॅशसेटमध्ये घालावे लागतील, म्हणून हॅशसेटमध्ये आपल्याकडे पुढील मूल्ये आहेतः

हॅशसेट: {9,5,2,6,8} // मुळात b ची सर्व मूल्ये [].

आम्ही अ‍ॅरे ए [] ओलांडू आणि त्यातील प्रत्येक घटक घेऊ आणि स्थिती तपासू.

i = 0, a [i] = 2

2 हॅशसेटमध्ये आहे, म्हणून ते मुद्रित होणार नाही.

i = 1, a [i] = 6

6 हॅशसेटमध्ये आहे, पुन्हा ते छापले जाणार नाही.

i = 2, a [i] = 8

8 हॅशसेटमध्ये आहे, ते मुद्रित केले जाणार नाहीत.

i = 3, a [i] = 9

9 हॅशसेटमध्ये आहे, म्हणून ते मुद्रित होणार नाही.

i = 4, a [i] = 5

5 हॅशसेटमध्ये आहे, पुन्हा ते छापले जाणार नाही.

i = 5, a [i] = 4

4 हॅशसेटमध्ये नाही, म्हणून यावेळेस हे प्रिंट होईल म्हणजे अ‍ॅरे मध्ये उपस्थित असलेली संख्या आहे [] परंतु अ‍ॅरे बी मध्ये नाही [] कारण मुळात हॅशसेट हे अ‍ॅरे बीचा क्लोन आहे [आणि] आपले आउटपुट '4' व्हा.

प्रथम अ‍ॅरे मध्ये उपस्थित असलेले आणि दुसर्‍या क्रमांकावर नसलेले घटक शोधण्यासाठी सी ++ कोड

#include<unordered_set>
#include<iostream>
using namespace std;

void getMissingElement(int A[], int B[], int l1, int l2)
{
  unordered_set <int> myset;

  for (int i = 0; i < l2; i++)
    myset.insert(B[i]);

  for (int j = 0; j < l1; j++)
    if (myset.find(A[j]) == myset.end())
      cout << A[j] << " ";
}
int main()
{
    int a[] = { 9, 2, 3, 1, 4, 5 };
    int b[] = { 2, 4, 1, 9 };
  int l1 = sizeof(a) / sizeof(a[0]);
  int l2 = sizeof(b) / sizeof(b[0]);
  getMissingElement(a, b, l1, l2);
  return 0;
}
3 5

पहिल्या अ‍ॅरेमध्ये अस्तित्वात असलेले आणि दुसर्‍या नसलेले घटक शोधण्यासाठी जावा कोड

import java.util.HashSet;
import java.util.Set;

class missingElement
{
    public static void getMissingElement(int A[], int B[])
    {
        int l1 = A.length;
        int l2 = B.length;

        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < l2; i++)
            set.add(B[i]);

        for (int i = 0; i < l1; i++)
            if (!set.contains(A[i]))
                System.out.print(A[i]+" ");
    }
    public static void main(String []args)
    {
        int a[] = { 9, 2, 3, 1, 4, 5 };
        int b[] = { 2, 4, 1, 9 };

        getMissingElement(a, b);
    }
}
3 5

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन) जेथे “एन” अ‍ॅरे 1 मधील घटकांची संख्या आहे. कारण समाविष्ट करण्यासाठी आणि शोधण्यासाठी हॅशसेटचा वापर केल्याने आम्हाला हे ऑपरेशन ओ (1) मध्ये करण्यास अनुमती देते. अशा प्रकारे वेळेची जटिलता रेषात्मक असते.

स्पेस कॉम्प्लेक्सिटी

ओ (एन) जेथे “एन” अ‍ॅरे 1 मधील घटकांची संख्या आहे. आपण दुसर्‍या अ‍ॅरेचे घटक संचित करत आहोत. अशा प्रकारे आवश्यक जागा दुसर्‍या अ‍ॅरेच्या आकाराप्रमाणेच आहे.