நகல் II லீட்கோட் தீர்வு உள்ளது


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அமேசான் பேஸ்புக் கூகிள்
அணி ஹேஷிங் நெகிழ் சாளரம்

சிக்கல் அறிக்கை

இந்த சிக்கலில் எங்களுக்கு ஒரு வழங்கப்படுகிறது வரிசை முழு எண்ணின் மற்றும் குறைந்தபட்சம் தூரத்தில் ஏதேனும் நகல் உறுப்பு இருக்கிறதா என்று நாம் சோதிக்க வேண்டும் k ஒருவருக்கொருவர்.
அதாவது அந்த இரண்டு ஒரே தனிமத்தின் குறியீடுகளுக்கிடையேயான வேறுபாடு k க்கு சமமாக இருக்க வேண்டும்.
அல்லது,  எண்கள் [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 எண்கள் [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 லீட்கோட் தீர்வைக் கொண்ட சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

O (n * min (k, n)): வரிசையின் ஒவ்வொரு உறுப்புக்கும் நிமிடம் (கே, என்) உறுப்புகளைக் கடந்து செல்கிறோம். எனவே நேர சிக்கலானது O (n * min (k, n)) ஆக இருக்கும்.

விண்வெளி சிக்கலானது 

ஓ (1): நிலையான இடம்.

அணுகுமுறை 2 (நெகிழ் சாளரம்)

நாம் பார்க்க முடியும் என நாம் வரிசையின் உறுப்புகளுக்கு ஒன்றுக்கு மேற்பட்ட முறை செல்கிறோம், இது அதன் நேர சிக்கலை அதிகரிக்கிறது. O (n) க்கான நேரத்தைக் குறைக்க ஒவ்வொரு உறுப்புக்கும் ஒரு முறை மட்டுமே நாம் பார்வையிட வேண்டும்.

அதற்காக நாம் என்ன செய்ய முடியும் என்பது முந்தைய ஒரு நெகிழ் சாளரத்தை வைத்திருக்க முடியும் k ஒவ்வொரு முறையும் வரிசையின் எந்த உறுப்புகளையும் நாங்கள் பார்வையிடும்போது ஒரு ஹாஷ் செட்டைப் பயன்படுத்தும் கூறுகள். இதைச் செய்வதன் மூலம், நாம் பார்வையிடும் தற்போதைய உறுப்புக்கு சமமான தொகுப்பில் ஒரு உறுப்பு இருக்கிறதா என்று முந்தைய கே உறுப்புகளின் தொகுப்பிலிருந்து எளிதாக சரிபார்க்கலாம். தொகுப்பில் ஒன்றைக் கண்டால், அந்த நேரத்தில் நாம் உண்மைக்குத் திரும்புவோம். இல்லையெனில், தொகுப்பில் தற்போதைய உறுப்பைச் செருகுவோம், கடைசியாக பார்வையிட்ட உறுப்பை தொகுப்பிலிருந்து அகற்றுவோம், இதனால் நாம் எப்போதும் இருப்போம் k எங்கள் தொகுப்பில் முந்தைய கூறுகள்.

கீழே உள்ள படத்தில் ஒரு உதாரணத்தைக் காணலாம்:

நகல் II லீட்கோட் தீர்வு உள்ளது

அல்காரிதம்

  1. உருவாக்கவும் ஹாஷ் செட் சேமிப்பதற்காக k முந்தைய கூறுகள்.
  2. கொடுக்கப்பட்ட வரிசையின் ஒவ்வொரு உறுப்பு எண்களுக்கும் [i] ஒரு சுழற்சியில் பயணிக்கவும்.
    • ஹாஷ் செட்டில் ஏற்கனவே எண்கள் உள்ளனவா என்பதை சரிபார்க்கவும் [i] இல்லையா. எண்கள் [i] தொகுப்பில் இருந்தால் (அதாவது நகல் உறுப்பு சமமான தூரத்திற்கு குறைவாக இருக்கும் k ), பின்னர் உண்மைக்குத் திரும்புக. தொகுப்பில் எண்களை [i] சேர்க்கவும்.
    • தொகுப்பின் அளவு k ஐ விட அதிகமாக இருந்தால், கடைசியாக பார்வையிட்ட உறுப்பை (எண்கள் [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 லீட்கோட் தீர்வைக் கொண்ட சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

ஓ (ந): ஒவ்வொரு உறுப்புகளையும் ஒரு முறை மட்டுமே பார்வையிடும்போது, ​​ஒரு உறுப்பைச் சேர்ப்பதும் ஒரு உறுப்பை அகற்றுவதும் ஹாஷ் செட் நேர சிக்கலில் நிலையான நேரத்தை O (n) ஆகக் குறைக்கிறது.

விண்வெளி சிக்கலானது 

ஓ (நிமிடம் (க, ந)): கே கூறுகளை ஹாஷ் தொகுப்பில் அதிகபட்சமாக சேமித்து வருகிறோம். K> n எனில், n உறுப்பு மட்டுமே அதிகபட்சமாக தொகுப்பில் சேமிக்கப்படும்.