डुप्लिकेट II लीटकोड सोल्यूशन आहे


अडचण पातळी सोपे
वारंवार विचारले ऍमेझॉन फेसबुक Google
अरे हॅशिंग सरकता विंडो

समस्या विधान

या समस्येमध्ये आम्हाला एक दिले जाते अॅरे पूर्णांक संख्या आहे आणि कमीतकमी अंतरावर असलेले कोणतेही डुप्लिकेट घटक अस्तित्त्वात आहेत का ते तपासावे लागेल k एकमेकांना.
म्हणजेच त्या दोन समान घटकाच्या निर्देशांकांमधील फरक के के पेक्षा कमी असावा.
किंवा,  संख्या [i] == क्रमांक [j] आणि एबीएस (आयजे) <= के

उदाहरण

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

स्पष्टीकरण:

अनुक्रमणिका 0 आणि 3 मधील घटक समान आहेत आणि 3 - 0 <= के.

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

दृष्टीकोन 1 (क्रूर शक्ती)

जर आपण ब्रूट फोर्स अप्रोचबद्दल बोललो तर आपण फक्त दोन लूप वापरुन प्रोग्रॅम कार्यान्वित करू शकतो आणि त्यामध्ये कुठलाही एलिमेंट अस्तित्वात आहे की नाही याची एरेच्या प्रत्येक घटकापासून दूर के अंतरापर्यंत तपासू शकतो.
जर कोणताही घटक सध्याच्या घटकाइतकाच आढळला असेल तर आपण खर्‍यास परत येऊ अन्यथा आम्ही खोटे परत करतो.

अल्गोरिदम

  1. प्रत्येक घटकासाठी लूप चालवा संख्या [i] दिलेल्या अ‍ॅरेचे.
  2. या लूपच्या आत पुन्हा लूप चालवा आणि तेथून सर्व घटक आक्रमित करा j = i + 1 ते j = i + के आणि त्याचे मूल्य तुलना करा संख्या [i]
    • If संख्या [j] == संख्या [i] मग खरे परत. जसे आपल्याला एक घटक सापडला आहे.
  3. शेवटी जेव्हा कोणतेही डुप्लिकेट घटक सापडले नाहीत तर फंक्शनमधून बाहेर पडण्यापूर्वी खोटे परत जा.

डुप्लिकेट II लीटकोड सोल्यूशनची अंमलबजावणी

सी ++ प्रोग्राम

#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

डुप्लिकेट II लीटकोड सोल्यूशनसाठी कॉम्प्लेक्सिटी विश्लेषण

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

ओ (एन * मिनिट (के, एन)): अ‍ॅरेच्या प्रत्येक घटकासाठी आम्ही मि (के, एन) घटक शोधत आहोत. म्हणून वेळ जटिलता ओ (एन * मि (के, एन)) असेल.

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

ओ (1): सतत जागा.

दृष्टीकोन 2 (सरकता विंडो)

जसे आपण पाहू शकतो की आपण अ‍ॅरेच्या घटकांकडे एकापेक्षा जास्त वेळा जात आहोत ज्यामुळे त्याची वेळ जटिलता वाढेल. ओ (एन) ची वेळ कमी करण्यासाठी आम्ही प्रत्येक घटकास फक्त एकदाच भेट दिली पाहिजे.

त्यासाठी आपण आधीची स्लाइडिंग विंडो ठेवू शकतो k हॅश सेट वापरणारे घटक जेव्हा आम्ही अ‍ॅरेच्या कोणत्याही घटकास भेट देत असतो. असे केल्याने आम्ही पूर्वीच्या के घटकांच्या सेटमधून सहजपणे तपासू शकतो की जर सेटमध्ये एखादा घटक अस्तित्वात असेल तर ज्याला आपण सध्या भेट देत आहोत त्या घटकांसारखेच आहे. जर आम्हाला एखादे सेट आढळले तर त्याक्षणी आम्ही खरा आहोत. अन्यथा आम्ही सेटमध्ये वर्तमान घटक समाविष्ट करू आणि आपल्याकडे नेहमीच असायला हवा म्हणून घटक सेटमधून काढून टाकू k आमच्या सेटमधील मागील घटक

खाली दिलेल्या आकृतीत उदाहरण पाहू या:

डुप्लिकेट II लीटकोड सोल्यूशन आहे

अल्गोरिदम

  1. तयार हॅश सेट साठवण्यासाठी k मागील घटक
  2. लूपमध्ये दिलेल्या अ‍ॅरेच्या प्रत्येक घटकाच्या संख्येसाठी [i] ट्रॅव्हर्स करा.
    • हॅश सेटमध्ये आधीपासून क्रमांक आहेत [i] किंवा नाही हे तपासा. संख्या मध्ये [i] संचात असल्यास (म्हणजेच डुप्लिकेट घटक समान पेक्षा कमी अंतरावर उपस्थित असेल k ) नंतर सत्य परत करा. अन्यथा सेटमध्ये क्रमांक जोडा [i].
    • जर सेटचा आकार के पेक्षा जास्त झाला तर शेवटचा भेट दिलेला घटक (क्रमांक [ik]) सेटमधून काढा.
  3. शेवटी जेव्हा कोणतेही डुप्लिकेट घटक सापडले नाहीत तर फंक्शनमधून बाहेर पडण्यापूर्वी खोटे परत जा.

डुप्लिकेट II लीटकोड सोल्यूशनची अंमलबजावणी

सी ++ प्रोग्राम

#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

डुप्लिकेट II लीटकोड सोल्यूशनसाठी कॉम्प्लेक्सिटी विश्लेषण

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

ओ (एन): जेव्हा आम्ही प्रत्येक घटकास फक्त एकदा भेट देतो आणि असे मानते की घटक जोडणे आणि घटक काढणे हॅश सेट वेळ जटिलतेमध्ये फक्त ओ (एन) पर्यंत कमी वेळ घेते.

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

ओ (मि (के, एन)): आम्ही हॅश सेटमध्ये के एलिमेंट्स जास्तीत जास्त साठवत आहोत. जर के <एन असेल तर सेटमध्ये फक्त एन घटक संग्रहित केले जातील.