k- वें बढ़ते हुए क्रम में गायब तत्व जो किसी दिए गए अनुक्रम में मौजूद नहीं है  


कठिनाई स्तर आसान
में अक्सर पूछा गढ़ Expedia फैब FactSet आईबीएम एसएपी लैब्स
ऐरे हैश खोजना

समस्या "बढ़ते क्रम में k- वें अनुपलब्ध तत्व जो किसी दिए गए अनुक्रम में मौजूद नहीं है" बताता है कि आपको दो सरणियाँ दी गई हैं। उनमें से एक को आरोही क्रम में व्यवस्थित किया गया है और दूसरा सामान्य अनारक्षित सरणी है, जिसमें नंबर k है। के टी लापता तत्व को ढूंढें जो सामान्य अनुक्रम में मौजूद नहीं है लेकिन बढ़ते क्रम अनुक्रम सरणी में मौजूद है।

उदाहरण  

k- वें बढ़ते हुए क्रम में गायब तत्व जो किसी दिए गए अनुक्रम में मौजूद नहीं है

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

व्याख्या

बढ़ते हुए क्रम में संख्याएँ जो दी गई सारणी में मौजूद नहीं हैं, 0,8,14 हैं।

कश्मीरth लापता संख्या अर्थात, २nd संख्या 8 है

बढ़ते क्रम में k-th लापता तत्व को खोजने के लिए एल्गोरिथ्म जो किसी दिए गए अनुक्रम में मौजूद नहीं है  

  1. डिक्लेयर ए हैशसेट.
  2. दूसरे एरे के सभी तत्वों को हैशसेट में डालें।
  3. सेट याद आ रही है 0 लिए.
  4. बढ़ते अनुक्रमिक सरणी का पता लगाते समय, जांचें:
    1. यदि किसी सेट में अनुक्रमिक सरणी तत्व नहीं है
      1. अनुपलब्ध मान को 1 से बढ़ाएँ।
      2. जाँच करें कि क्या अनुपलब्ध मान के बराबर है।
        • यदि सही है, तो उस सरणी को वापस करें [i]।
  5. पाश से बाहर, वापसी -1।

व्याख्या

आपको दो सरणियाँ और एक नंबर k दिया जाता है। दो सरणियों में से एक एक बढ़ते अनुक्रम है और दूसरा एक सामान्य अनसुलझा अनुक्रम है। समस्या कथन यह कहता है कि आपको क्रमबद्ध अनुक्रम सरणी में kth अनुपस्थित तत्व को खोजना है जो कि मौजूद सरणी में मौजूद नहीं है।

यह भी देखें
Array में सबसे बड़ा d ज्ञात कीजिए कि a + b + c = d

हम इसके लिए एक सेट का उपयोग करने जा रहे हैं। हम दूसरी सारणी को पार करने जा रहे हैं बी [] और सेट में इसके सभी मूल्य डालें। ऐसा इसलिए है क्योंकि हम इसे बाद में देख सकते हैं और पहले सरणी के साथ सेट की तुलना कर सकते हैं ए[]। एरे को ट्रैस करते समय [], अगर सेट में ए [i] एरे का वह विशेष मूल्य नहीं होता है। हम का मान बढ़ाते हैं याद आ रही है 1 से और एक साथ जाँच करें कि क्या अनुपलब्ध दिए गए नंबर k के बराबर है। यदि ऐसा होता है, तो हम पहले एरे के तत्व को वापस कर सकते हैं।

आइए एक उदाहरण पर विचार करें और इसे समझें।

उदाहरण

सरणी [] = [0, 2, 4, 6, 8, 10, 12, 14]

b [] = [४, १०, ६, १२, २]

कश्मीर = 2

एल्गोरिथ्म के अनुसार, हमें सरणी बी [] तत्वों को सेट में रखना होगा। हम इसे सरणी b [] पर ट्रेस करके करेंगे।

हमारा सेट {4, 10, 6, 12, 2} बन जाएगा

हमें सरणी [[] तत्वों को ट्रेस करना होगा और जांचना होगा कि क्या सेट में गिरफ्तारी नहीं है [i] तत्व,

i = 0, गिरफ्तारी [i] = 0

सेट में यह सम्‍मिलित नहीं है इसलिए यह अनुपलब्ध हो जाएगा

याद कर सकते हैं = 1, अगर अनुपलब्ध जाँच करें == k, यह गलत है।

i = 1, गिरफ्तारी [i] = 2

सेट में वह मान '2' है, इसलिए यह कुछ भी नहीं करता है।

i = 2, गिरफ्तारी [i] = 4

सेट में वह मान '4' है, इसलिए यह कुछ भी नहीं करता है।

i = 3, गिरफ्तारी [i] = 6

सेट में वह मान '6' है, इसलिए यह कुछ भी नहीं करता है।

i = 4, गिरफ्तारी [i] = 8

सेट में 8 शामिल नहीं है, इसलिए यह अनुपलब्ध हो जाएगा

मिसिंगाउंट = 2, चेक करें कि क्या लापता है == के, यह सच है, इसलिए यह गिरफ्तारी वापस आ जाएगी [i] जो कि '8' है,

आउटपुट 8 हो जाएगा।

यह भी देखें
लगातार समय सीमा एक सरणी पर ऑपरेशन जोड़ें

कोड  

C ++ कोड बढ़ते हुए क्रम में k-th लापता तत्व को खोजने के लिए जो किसी दिए गए अनुक्रम में मौजूद नहीं है

#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

जावा कोड बढ़ते हुए क्रम में k-th लापता तत्व को खोजने के लिए जो किसी दिए गए अनुक्रम में मौजूद नहीं है

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

जटिलता विश्लेषण  

समय जटिलता

O (n1 + n2) जहां "एन 1" और "एन 2" array1 और array2 की लंबाई है। चूंकि हमने दोनों एरे से सभी तत्वों का पता लगाया है। समय जटिलता रैखिक है।

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

O (n2) जहां "एन 2" array2 की लंबाई है। क्योंकि हमने दूसरे सरणी के तत्वों को केवल HashSet में संग्रहीत किया है, आवश्यक स्थान भी रैखिक है।

यह भी देखें
कोयल हाशिंग