इसमें डुप्लिकेट II Leetcode Solution शामिल है


कठिनाई स्तर आसान
में अक्सर पूछा वीरांगना Facebook गूगल
ऐरे hashing फिसलने वाली खिडकी

समस्या का विवरण

इस समस्या में हमें एक सरणी पूर्णांक और हमें यह जांचना होगा कि क्या कोई डुप्लिकेट तत्व मौजूद है जो कम से कम दूरी पर है k एक दूसरे को।
अर्थात उन दो समान तत्वों के सूचकांकों के बीच का अंतर k के बराबर कम होना चाहिए।
या,  nums [i] == संख्या [j] और abs (ij) <= k

उदाहरण

nums = [1,2,3,1], k = 3
true

स्पष्टीकरण:

सूचकांक 0 और 3 पर तत्व समान है, और 3 - 0 <= k।

nums = [1,2,3,1,2,3], k = 2
false

दृष्टिकोण 1 (जानवर बल)

यदि हम जानवर बल दृष्टिकोण के बारे में बात करते हैं, तो हम बस दो छोरों का उपयोग करके कार्यक्रम को लागू कर सकते हैं और सरणी के प्रत्येक तत्व से दूरी k के लिए सही से जांच सकते हैं कि कोई तत्व मौजूद है या नहीं।
यदि कोई तत्व वर्तमान तत्व के समान पाया जाता है तो हम वापस लौट जाते हैं अन्यथा हम असत्य पर लौट आते हैं।

कलन विधि

  1. प्रत्येक तत्व के लिए एक लूप चलाएँ अंक [i] दिए गए सरणी के।
  2. इस लूप के अंदर फिर से लूप के लिए दौड़ते हैं और सभी तत्वों को पीछे छोड़ते हैं j = i + 1 सेवा मेरे j = i + k और इसके मूल्य की तुलना करें संख्या [i]।
    • If nums [j] == nums [i] फिर सच मानो। जैसा कि हमने एक तत्व पाया है।
  3. अंत में जब कोई डुप्लिकेट तत्व नहीं मिलता है, तो फ़ंक्शन से बाहर निकलने से पहले झूठी वापस आ जाएं।

डुप्लिकेट II Leetcode समाधान के लिए कार्यान्वयन

C ++ प्रोग्राम

#include <bits/stdc++.h>
using namespace std;

bool containsNearbyDuplicate(vector<int>& nums, int k) 
{
    for(int i=0;i<nums.size();i++)
        for(int j=i+1;j<nums.size() && j<=i+k;j++)
        {
            if(nums[j]==nums[i])
                return true;
        }

    return false;
}

int main() 
{
    vector<int> nums={1,2,3,1};
    int k=3;
    if(containsNearbyDuplicate(nums, k))
        cout<<"true"<<endl;
    else
        cout<<"false"<<endl;

   return 0; 
}
true

जावा प्रोग्राम

class Rextester{
    
    public static boolean containsNearbyDuplicate(int[] nums, int k) 
    {
        for(int i=0;i<nums.length;i++)
            for(int j=i+1;j<nums.length && j<=i+k;j++)
            {
                if(nums[j]==nums[i])
                    return true;
            }

        return false;

    }
    
    public static void main(String args[])
    {
       	int[] nums={1,2,3,1};
        int k=3;
        System.out.println(containsNearbyDuplicate(nums,k) );
    }
}
true

द्वैध द्वितीय Leetcode समाधान के लिए जटिलता विश्लेषण

समय जटिलता

ओ (एन * मिनट (के, एन)): हम सरणी के प्रत्येक तत्व के लिए न्यूनतम (k, n) तत्वों का पता लगा रहे हैं। इसलिए समय की जटिलता ओ (एन * मिनट (के, एन)) होगी।

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

ओ (1): लगातार जगह।

दृष्टिकोण 2 (स्लाइडिंग विंडो)

जैसा कि हम देख सकते हैं कि हम सरणी के तत्वों के लिए एक से अधिक बार जा रहे हैं जो इसकी समय जटिलता को बढ़ाता है। O (n) का समय कम करने के लिए हमें प्रत्येक तत्व के लिए केवल एक बार जाना चाहिए।

इसके लिए हम जो कर सकते हैं वह है कि हम पिछले की स्लाइडिंग विंडो रख सकते हैं k Hash का उपयोग करने वाले तत्व हर बार हम ऐरे के किसी भी तत्व पर जा रहे हैं। ऐसा करने से हम पिछले k तत्वों के सेट से आसानी से देख सकते हैं कि क्या सेट में कोई तत्व मौजूद है जो कि वर्तमान तत्व के समान है जो हम देख रहे हैं। अगर हमें सेट में एक मिला, तो उस पल में हम सच में लौटेंगे। और हम वर्तमान तत्व को सेट में सम्मिलित करेंगे और अंतिम विज़िट किए गए तत्व को भी सेट से हटा देंगे ताकि हमारे पास हमेशा रहे k हमारे सेट में पिछले तत्व।

नीचे दिए गए चित्र में एक उदाहरण देखें:

इसमें डुप्लिकेट II Leetcode Solution शामिल है

कलन विधि

  1. बनाओ हैश सेट भंडारण के लिए k पिछले तत्व।
  2. लूप में दिए गए एरे के हर एलिमेंट नंबर्स [i] के लिए ट्रैवर्स।
    • जांचें कि क्या हैश सेट में पहले से ही अंक [i] हैं या नहीं। यदि अंक [i] सेट में मौजूद है (यानी डुप्लिकेट तत्व बराबर से कम दूरी पर मौजूद है k ), फिर वापस लौटें। सेट में अंक [i] जोड़ दें।
    • यदि सेट का आकार k से अधिक हो जाता है तो सेट से अंतिम विज़िट किए गए तत्व (अंक [ik]) को हटा दें।
  3. अंत में जब कोई डुप्लिकेट तत्व नहीं मिलता है, तो फ़ंक्शन से बाहर निकलने से पहले झूठी वापस आ जाएं।

डुप्लिकेट II Leetcode समाधान के लिए कार्यान्वयन

C ++ प्रोग्राम

#include <bits/stdc++.h>
using namespace std;

bool containsNearbyDuplicate(vector<int>& nums, int k) 
{
    unordered_set<int> set;
    for(int i=0;i<nums.size();i++)
    {
        if(set.count(nums[i])) return true;
        set.insert(nums[i]);

        if(set.size()>k)
            set.erase(nums[i-k]);
    }

    return false;
}

int main() 
{
    vector<int> nums={1,2,3,1};
    int k=3;
    if(containsNearbyDuplicate(nums, k))
        cout<<"true"<<endl;
    else
        cout<<"false"<<endl;

   return 0; 
}
true

जावा प्रोग्राम

#include <bits/stdc++.h>
using namespace std;

bool containsNearbyDuplicate(vector<int>& nums, int k) 
{
    unordered_set<int> set;
    for(int i=0;i<nums.size();i++)
    {
        if(set.count(nums[i])) return true;
        set.insert(nums[i]);

        if(set.size()>k)
            set.erase(nums[i-k]);
    }

    return false;
}

int main() 
{
    vector<int> nums={1,2,3,1};
    int k=3;
    if(containsNearbyDuplicate(nums, k))
        cout<<"true"<<endl;
    else
        cout<<"false"<<endl;

   return 0; 
}
true

द्वैध द्वितीय Leetcode समाधान के लिए जटिलता विश्लेषण

समय जटिलता

पर) : जैसा कि हम प्रत्येक तत्व का केवल एक बार दौरा करते हैं और यह मानते हैं कि एक तत्व को जोड़ने और एक तत्व को हटाने में निरंतर समय लगता है समय जटिलता केवल O (n) में कम हो जाती है।

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

O (न्यूनतम (k, n)): हम हैश सेट में अधिकतम पर कश्मीर तत्वों का भंडारण कर रहे हैं। यदि k> n है तो केवल n तत्व अधिकतम पर सेट में संग्रहीत किया जाएगा।