के-थ्रु बढ्दो अनुक्रममा हराइरहेको तत्व जुन दिइएको क्रममा छैन


कठिनाई तह सजिलो
बारम्बार सोधिन्छ Citadel Expedia फेब तथ्य आईबीएम SAP ल्याबहरू
एरे हैश खोजी

समस्या "के-थ्रु अनुक्रम बढ्दो अनुक्रममा दिईएको अनुक्रममा उपस्थित छैन" भन्ने कुराले तपाईंलाई दुई एर्रेहरू दिएको छ। ती मध्ये एक आरोही क्रममा व्यवस्थित गरीएको छ र अर्को सामान्य अनसोर्टेड एर्रे नम्बर के साथ। Kth हराइरहेको तत्व फेला पार्नुहोस् जुन सामान्य अनुक्रममा छैन तर बढ्दो क्रम अनुक्रम एरेमा अवस्थित छ।

उदाहरणका

के-थ्रु बढ्दो अनुक्रममा हराइरहेको तत्व जुन दिइएको क्रममा छैन

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

स्पष्टीकरण

बढ्दो अनुक्रममा संख्याहरू जुन दिइएको एर्रेमा उपस्थित छैन, ०,0,8,14,१XNUMX हो।

केth हराइरहेको संख्या जस्तै, २nd संख्या is हो

एल्गोरिथ्म बढ्दो अनुक्रममा K-th हराइरहेको तत्व फेला पार्न जुन दिइएको अनुक्रममा उपस्थित छैन

  1. घोषणा गर्नुहोस् ह्याससेट.
  2. दोस्रो एर्रेको एलिमेन्ट्स ह्याससेटमा राख्नुहोस्।
  3. सेट अनुपस्थिति 0 मा।
  4. बढ्दो अनुक्रमिक एर्रे ट्र्याभरिंग गर्दा, जाँच गर्नुहोस्:
    1. यदि सेटमा कुनै अनुक्रमिक एर्रे एलिमेन्ट समावेश छैन
      1. १ द्वारा हराएको काउन्ट मान बढाउनुहोस्।
      2. जाँच गर्नुहोस् यदि हराइरहेको काउन्ट मान k k बराबर छ।
        • यदि सहि छ भने, त्यो एरे फिर्ता गर्नुहोस् [i]।
  5. लूपबाट बाहिर, फिर्ता -१।

स्पष्टीकरण

तपाईंलाई दुई एर्रे र एक संख्या के दिइन्छ। दुई एर्रे मध्ये एक बढ्दो अनुक्रम हो र अर्को एउटा सामान्य अनसोर्टेड अनुक्रम हो। समस्या कथन भन्छ कि तपाईंले क्रमबद्ध क्रम एरेमा Kth हराइरहेको तत्व फेला पार्नु पर्छ जुन क्रमबद्ध एर्रेमा छैन।

हामी यसको लागी एक सेट प्रयोग गर्नेछौं। हामी दोस्रो एरे पार गर्न जाँदैछौं b [] र सेटमा यसको सबै मान सम्मिलित गर्नुहोस्। यो किनभने हामी यसलाई पछि जाँच्न सक्छौं र सेटलाई पहिलो एर्रेसँग तुलना गर्न सक्छौं एक []। एर्रे ट्र्याभरिंग गर्ने क्रममा []], यदि सेटमा एर्रेको [i] को त्यो खास मान छैन भने। हामीले यसको मान बढायौं अनुपस्थिति १ द्वारा र एकसाथ जाँच गर्नुहोस् यदि अनुपलब्ध गणना दिइएको संख्या k बराबर हुन्छ। यदि यसले गर्छ, हामी पहिलो एर्रेको त्यो एलिमेन्ट फर्काउन सक्छौं।

हामी एउटा उदाहरण विचार गरौं र यसलाई बुझौं।

उदाहरणका

एर्रे एक [] = [०, २,,,,,,, १०, १२, १]]

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

k = 2

एल्गोरिथ्मको रूपमा, हामीले एरे b [] एलिमेन्टहरू सेटमा राख्नु पर्छ। हामी यो एरे b [] बाट पार गरेर गर्नेछौं।

हाम्रो सेट {,, १०,,, १२, २ become हुनेछ

हामीले एर्रे ए [] एलिमेन्टहरू पार गर्नुपर्दछ र जाँच गर्नुहोस् कि सेटमा एर [i] एलिमेन्ट छैन,

i = 0, एर [i] = ०

सेटमा समावेश छैन त्यसैले यसले हराएको गणना = बढाएको गणना +१ बढाउनेछ

C। missingCountCC missing missing = = = = =। = =।।।।।। .ountountountountount।।। .ount।,।,,,।,,,,,,,,,,,,,,,,,।,।।।।।।।।।।।

i = 1, एर [i] = ०

सेटमा त्यो मान '२' हुन्छ, त्यसैले यसले केहि गर्दैन।

i = 2, एर [i] = ०

सेटमा त्यो मान '२' हुन्छ, त्यसैले यसले केहि गर्दैन।

i = 3, एर [i] = ०

सेटमा त्यो मान '२' हुन्छ, त्यसैले यसले केहि गर्दैन।

i = 4, एर [i] =।

सेटमा contain समावेश गर्दैन, त्यसैले यसले छुटेकाउन्ट = अनुपलब्ध खाता +१ लाई बढाउनेछ

अनुपलब्ध खाता = २, जाँच गरौं भने हराइरहेको गणना == k, यो सहि छ त्यसैले यो एर फिर्ता हुनेछ [i] त्यो '' 'हो,

आउटपुट become हुनेछ।

कोड

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) जहाँ "N1" र "N2" array1 र array2 को लम्बाई हो। किनकि हामी दुबै एर्रेबाट सबै एलिमेन्टहरू ट्र्याभर्स गरेका छौं। समय जटिलता रैखिक छ।

ठाउँ जटिलता

O (n2) जहाँ "N2" एरे २ को लम्बाई हो। किनकि हामीले दोस्रो एरेको एलिमेन्ट्स मात्र ह्याशसेटमा भण्डारण गरेका छौं, आवश्यक ठाउँ पनि रैखिक छ।