ડુપ્લિકેટ II લેટકોડ સોલ્યુશન શામેલ છે


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે એમેઝોન ફેસબુક Google
અરે હેશિંગ બારણું વિંડો

સમસ્યા નિવેદન

આ સમસ્યામાં અમને એક આપવામાં આવે છે એરે પૂર્ણાંકો છે અને આપણે ત્યાં તપાસ કરવી પડશે કે ત્યાં કોઈ ડુપ્લિકેટ તત્વ છે કે જે ઓછામાં ઓછા અંતરે છે k એક બીજા ને.
એટલે કે તે બે સમાન તત્વના સૂચકાંકો વચ્ચેનો તફાવત 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 (બ્રુટ ફોર્સ)

જો આપણે બ્રુટ ફોર્સ એપ્રોચ વિશે વાત કરીશું, તો આપણે ફક્ત બે લૂપ્સનો ઉપયોગ કરીને પ્રોગ્રામને અમલમાં મૂકી શકીએ છીએ અને એરેના દરેક તત્વને ત્યાંથી કોઈ અંતર K સુધી તપાસીશું કે ત્યાં કોઈ તત્વ હાજર છે કે નહીં.
જો કોઈપણ તત્વ વર્તમાન તત્વ સમાન હોય છે, તો અમે સાચું પાછા ફરો અન્યથા આપણે ખોટા વળગીએ છીએ.

અલ્ગોરિધમ

  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].
    • જો સમૂહનું કદ 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 લેટકોડ સોલ્યુશન માટેના જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન): જેમ કે આપણે દરેક તત્વની માત્ર એક જ વાર મુલાકાત લઈએ છીએ અને એમ માનીએ છીએ કે તત્વ ઉમેરવું અને તત્વને દૂર કરવું એ હેશ સેટ સમય જટિલતામાં સતત સમય લે છે જે ફક્ત ઓ (એન) સુધી ઘટાડે છે.

અવકાશ જટિલતા 

ઓ (મિનિટ (કે, એન)): અમે હેશ સેટમાં મહત્તમ પર k એલિમેન્ટ્સ સ્ટોર કરીએ છીએ. જો કે> એન પછી ફક્ત n તત્વ મહત્તમના સેટમાં સંગ્રહિત થશે.