वाढणार्‍या क्रमामध्ये के-थ्री गहाळ घटक जो दिलेल्या अनुक्रमात उपस्थित नाही


अडचण पातळी सोपे
वारंवार विचारले किल्ला यामध्ये फॅब फॅक्टसेट IBM एसएपी लॅब
अरे हॅश शोधत आहे

आपल्याला दिलेल्या वाढीच्या अनुक्रमात उपस्थित नसलेल्या वाढत्या क्रमामधील के-गहा घटकांची समस्या आपल्याला दोन अ‍ॅरे दिली असल्याचे सांगते. त्यातील एक चढत्या क्रमाने आणि के के सह एक सामान्य अनसोर्टेड अ‍ॅरे सह व्यवस्था केलेली आहे. Kth गहाळ घटक शोधा जो सामान्य अनुक्रमात नसलेला परंतु वाढणार्‍या ऑर्डर सीक्वेन्स अ‍ॅरेमध्ये असतो.

उदाहरण

वाढणार्‍या क्रमामध्ये के-थ्री गहाळ घटक जो दिलेल्या अनुक्रमात उपस्थित नाही

[0, 2, 4, 6, 8, 10, 12, 14]
[4, 10, 6, 12, 2 ]
k=2
8

स्पष्टीकरण

दिलेल्या अ‍ॅरेमध्ये उपस्थित नसलेल्या वाढत्या क्रमामधील संख्या 0,8,14 आहेत.

केth गहाळ संख्या म्हणजेच २nd संख्या 8 आहे

वाढणार्‍या अनुक्रमात के-व्यास गहाळ घटक शोधण्यासाठी अल्गोरिदम जो दिलेल्या अनुक्रमात उपस्थित नाही

  1. घोषित ए हॅशसेट.
  2. दुसर्‍या अ‍ॅरेचे सर्व घटक हॅशसेटमध्ये ठेवा.
  3. सेट करा गहाळ खाते 0 पर्यंत.
  4. वाढत्या क्रमांकाच्या अ‍ॅरेचा शोध घेताना, तपासा:
    1. सेटमध्ये कोणताही अनुक्रमिक अ‍ॅरे घटक नसल्यास
      1. गहाळ गणना मूल्य 1 ने वाढवा.
      2. हरवलेले खाते मूल्य के बरोबर आहे की नाही ते तपासा.
        • खरे असल्यास, ते अ‍ॅरे [i] परत करा.
  5. लूपमधून, परत -1.

स्पष्टीकरण

आपल्याला दोन अ‍ॅरे आणि एक क्रमांक के दिले आहे. दोन अ‍ॅरेपैकी एक म्हणजे वाढती अनुक्रम आणि दुसरा एक सामान्य अनुक्रमित क्रम आहे. समस्या विधान सांगते की आपल्याला क्रमवारी लावलेल्या अ‍ॅरेमध्ये नसलेले क्रमवारी अ‍ॅरेमध्ये kth गहाळ घटक शोधायचा आहे.

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

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

उदाहरण

अ‍ॅरे अ [] = [०, २,,,,,,, १०, १२, १]]

बी [] = [,, १०,,, १२, २]

के = 2

अल्गोरिदम नुसार, अ‍ॅरे बी [] एलिमेंट्स सेटमध्ये ठेवणे आवश्यक आहे. हे अ‍ॅरे बी [] चा ट्रॅव्हर्स करून करू.

आमचा सेट {4, 10, 6, 12, 2 become होईल

आम्हाला अ‍ॅरे ए [] एलिमेंटस पाठवणे आवश्यक आहे आणि सेटमध्ये अरर [i] एलिमेंट नसलेले हे तपासणे आवश्यक आहे,

i = 0, अरे [i] = 0

सेटमध्ये हे नसते म्हणून ते गमावलेली संख्या = गहाळखंडा +1 वाढवेल

अनुपलब्ध खाते = 1, गहाळखाते == के तपासले तर ते चुकीचे आहे.

i = 1, अरे [i] = 2

सेटमध्ये ती व्हॅल्यू '2' असते, त्यामुळे ते काही करत नाही.

i = 2, अरे [i] = 4

सेटमध्ये ती व्हॅल्यू '4' असते, त्यामुळे ते काही करत नाही.

i = 3, अरे [i] = 6

सेटमध्ये ती व्हॅल्यू '6' असते, त्यामुळे ते काही करत नाही.

i = 4, अरे [i] = 8

सेटमध्ये 8 नसतात, म्हणून ते गमावलेली संख्या = गहाळखंडा +1 वाढवते

अनुपलब्ध खाते = २, गहाळखाते == के तपासले तर ते सत्य आहे जेणेकरून ते परत येईल [i] म्हणजे 'that',

आउटपुट 8 होईल.

कोड

वाढीव अनुक्रमात के-थ्री गहाळ घटक शोधण्यासाठी सी ++ कोड जो दिलेल्या अनुक्रमात उपस्थित नाही

#include <unordered_set>
#include<iostream>

using namespace std;
int find(int A[], int B[], int k, int l1, int l2)
{
  unordered_set<int> myset;
  for (int i = 0; i < l2; i++)
    myset.insert(B[i]);

  int missingCount = 0;
  for (int i = 0; i < l1; i++) {
    if (myset.find(A[i]) == myset.end())
      missingCount++;
    if (missingCount == k)
      return A[i];
  }

  return -1;
}
int main()
{
    int a[] = { 0, 2, 4, 6, 8, 10, 12, 14};
    int b[] = { 4, 10, 6, 12, 2 };

  int l1 = sizeof(a) / sizeof(a[0]);
  int l2 = sizeof(b) / sizeof(b[0]);

  int k = 2;
  cout << find(a, b, k, l1, l2);
  return 0;
}
8

वाढणार्‍या अनुक्रमात के-थ्री गहाळ घटक शोधण्यासाठी जावा कोड जो दिलेल्या अनुक्रमात उपस्थित नाही

import java.util.LinkedHashSet;

class kthMissingElement
{
    public static int getMissingElement(int A[], int B[], int k, int l1, int l2)
    {
        LinkedHashSet<Integer> hashset = new LinkedHashSet<>();
        for (int i = 0; i < l2; i++)
            hashset.add(B[i]);

        int missingCount = 0;
        for (int i = 0; i < l1; i++)
        {
            if(!hashset.contains(A[i]) )
                missingCount++;
            if (missingCount == k)
                return A[i];
        }

        return -1;
    }
    public static void main(String[] args)
    {
        int a[] = { 0, 2, 4, 6, 8, 10, 12, 14};
        int b[] = { 4, 10, 6, 12, 2 };
        int l1 = a.length;
        int l2 = b.length;

        int k = 2;
        System.out.println(getMissingElement(a, b, k, l1, l2));
    }
}
8

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

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

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

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

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