सबसे छोटी विंडो ढूंढना

Question

दो एरे A[n] और B[m] दिए गए, मैं A में सबसे छोटी विंडो कैसे ढूंढ सकता हूं जिसमें B के सभी तत्व शामिल हैं।

मैं ओ (एन) समय में इस समस्या को हल करने की कोशिश कर रहा हूं लेकिन मुझे इसे करने में समस्या हो रही है। क्या इसे हल करने के लिए कोई अच्छी तरह से पता एल्गोरिदम या प्रक्रिया है।

Answer 1

गिनती की कॉल विंडो 'न्यूनतम' अगर इसे कम नहीं किया जा सकता है। यानी, अपनी बाएं सीमा को बढ़ाने या अपनी दाहिनी सीमा को कम करने के बाद यह अब वैध विंडो नहीं है (इसमें बी से सभी तत्व शामिल नहीं हैं)। आपके उदाहरण में तीन: [0, 2], [2, 6], [6, 7]

मान लें कि आपको पहले से ही बाईं ओर न्यूनतम विंडो [बाएं, दाएं] मिल गया है। ([0, 2] आपके उदाहरण में) अब हम इसे दाईं ओर स्लाइड करेंगे।

// count[x] tells how many times number 'x' 
// happens between 'left' and 'right' in 'A' 
while (right < N - 1) { 
    // move right border by 1 
    ++right; 
    if (A[right] is in B) { 
     ++count[A[right]]; 
    } 

    // check if we can move left border now 
    while (count[A[left]] > 1) { 
     --count[A[left]]; 
     ++left; 
    } 

    // check if current window is optimal 
    if (right - left + 1 < currentMin) { 
     currentMin = right - left + 1; 
    } 
} 

यह स्लाइडिंग काम करता है क्योंकि विभिन्न 'न्यूनतम' विंडो में एक दूसरे को शामिल नहीं किया जा सकता है।

Answer 2

तो m > n, AB के सभी तत्वों को शामिल नहीं कर सकते हैं (और इसलिए हम एक O(1) समाधान है)।

अन्यथा:

• B के हैश तालिका मानचित्रण तत्व अनुक्रम {0..m-1} (यह O(n) के बाद से है) बनाएँ।
• वर्तमान विंडो में B (प्रारंभ में 0) के सदस्यों के अवसरों की गणना करने के लिए C[m] एक सरणी बनाएं।

• के 0 तत्वों की संख्या को गिनने के लिए एक चर z बनाएं (m से प्रारंभ करें)।

• चर बनाएं s और e प्रारंभ और वर्तमान विंडो

• के अंत को निरूपित करने के जबकि e < n:
  • z तो अशून्य है, e को बढ़ा देते और C और z अद्यतन करें। O(1)
  • अन्यथा इस विंडो को एक संभावित समाधान के रूप में मानें (यानी यदि यह अब तक छोटा है, इसे स्टोर करें), तो s बढ़ाएं और C और z अपडेट करें। O(1)

The Loop कोई 2n की तुलना में अधिक पुनरावृत्तियों है दिखाया जा सकता है। तो पूरी बात O(n) है, मुझे लगता है।