ഡ്യൂപ്ലിക്കേറ്റ് II ലീറ്റ്കോഡ് പരിഹാരം അടങ്ങിയിരിക്കുന്നു  


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു ആമസോൺ ഫേസ്ബുക്ക് ഗൂഗിൾ
അൽഗോരിതം അറേ കോഡിംഗ് ഹാഷിംഗ് അഭിമുഖം അഭിമുഖം ലീട്ട് കോഡ് LeetCodeSolutions സ്ലൈഡിംഗ് വിൻഡോ

പ്രശ്നം പ്രസ്താവന  

ഈ പ്രശ്‌നത്തിൽ ഞങ്ങൾക്ക് ഒരു നൽകിയിട്ടുണ്ട് ശ്രേണി പൂർണ്ണസംഖ്യകളുടെ, കുറഞ്ഞത് അകലെയുള്ള ഏതെങ്കിലും തനിപ്പകർപ്പ് ഘടകങ്ങളുണ്ടോ എന്ന് പരിശോധിക്കേണ്ടതുണ്ട് 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 * മിനിറ്റ് (k, n)): അറേയിലെ ഓരോ ഘടകത്തിനും ഞങ്ങൾ min (k, n) ഘടകങ്ങൾ സഞ്ചരിക്കുന്നു. അതിനാൽ സമയ സങ്കീർണ്ണത O (n * min (k, n)) ആയിരിക്കും.

ബഹിരാകാശ സങ്കീർണ്ണത 

O (1): സ്ഥിരമായ ഇടം.

സമീപനം 2 (സ്ലൈഡിംഗ് വിൻഡോ)  

നമുക്ക് കാണാനാകുന്നതുപോലെ, അറേയുടെ ഘടകങ്ങളിലേക്ക് ഞങ്ങൾ ഒന്നിലധികം തവണ പോകുന്നു, അത് അതിന്റെ സമയ സങ്കീർണ്ണത വർദ്ധിപ്പിക്കുന്നു. O (n) ലേക്ക് സമയം കുറയ്ക്കുന്നതിന് ഓരോ ഘടകത്തിലും ഒരു തവണ മാത്രമേ ഞങ്ങൾ സന്ദർശിക്കൂ.

അതിനായി നമുക്ക് ചെയ്യാൻ കഴിയുന്നത് മുമ്പത്തെ സ്ലൈഡിംഗ് വിൻഡോ സൂക്ഷിക്കാൻ കഴിയും എന്നതാണ് k ഒരു ഹാഷ് സെറ്റ് ഉപയോഗിക്കുന്ന ഘടകങ്ങൾ ഓരോ തവണയും ഞങ്ങൾ അറേയുടെ ഏതെങ്കിലും ഘടകങ്ങൾ സന്ദർശിക്കുമ്പോൾ. ഇത് ചെയ്യുന്നതിലൂടെ, സെറ്റിൽ ഒരു ഘടകം നിലവിലുണ്ടെങ്കിൽ നമുക്ക് മുമ്പത്തെ കെ ഘടകങ്ങളുടെ കൂട്ടത്തിൽ നിന്ന് എളുപ്പത്തിൽ പരിശോധിക്കാൻ കഴിയും, അത് ഞങ്ങൾ സന്ദർശിക്കുന്ന നിലവിലെ ഘടകത്തിന് തുല്യമാണ്. ഒരെണ്ണം സെറ്റിൽ കണ്ടെത്തിയാൽ, ആ നിമിഷം ഞങ്ങൾ ശരിയാകും. അല്ലാത്തപക്ഷം ഞങ്ങൾ സെറ്റിലെ നിലവിലെ ഘടകം തിരുകുകയും അവസാനമായി സന്ദർശിച്ച ഘടകത്തെ സെറ്റിൽ നിന്ന് നീക്കംചെയ്യുകയും ചെയ്യുന്നതിലൂടെ ഞങ്ങൾക്ക് എല്ലായ്പ്പോഴും ഉണ്ടായിരിക്കും k ഞങ്ങളുടെ സെറ്റിലെ മുമ്പത്തെ ഘടകങ്ങൾ.

ഇതും കാണുക
പാസ്കലിന്റെ ത്രികോണം II ലീറ്റ്കോഡ് പരിഹാരം

ചുവടെയുള്ള ചിത്രത്തിൽ ഒരു ഉദാഹരണം കാണാം:

ഡ്യൂപ്ലിക്കേറ്റ് II ലീറ്റ്കോഡ് പരിഹാരം അടങ്ങിയിരിക്കുന്നു

അൽഗോരിതം

  1. സൃഷ്ടിക്കുക ഹാഷ് സെറ്റ് സംഭരിക്കുന്നതിന് k മുമ്പത്തെ ഘടകങ്ങൾ.
  2. തന്നിരിക്കുന്ന അറേയുടെ ഓരോ മൂലക സംഖ്യകൾക്കും ഒരു ലൂപ്പിൽ സഞ്ചരിക്കുക.
    • ഹാഷ് സെറ്റിൽ ഇതിനകം തന്നെ സംഖ്യകൾ ഉണ്ടോയെന്ന് പരിശോധിക്കുക [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): ഞങ്ങൾ ഓരോ ഘടകങ്ങളും ഒരുതവണ മാത്രം സന്ദർശിക്കുകയും ഒരു ഘടകം ചേർക്കുകയും ഒരു മൂലകം നീക്കംചെയ്യുകയും ചെയ്യുന്നത് ഹാഷ് സെറ്റ് സമയ സങ്കീർണ്ണതയിൽ സ്ഥിരമായി സമയമെടുക്കുമെന്ന് കരുതുക.

ബഹിരാകാശ സങ്കീർണ്ണത 

O (മിനിറ്റ് (k, n)): ഞങ്ങൾ k ഘടകങ്ങൾ ഹാഷ് സെറ്റിൽ പരമാവധി സംഭരിക്കുന്നു. K> n ആണെങ്കിൽ, n ഘടകം മാത്രമേ പരമാവധി സെറ്റിൽ സൂക്ഷിക്കുകയുള്ളൂ.