આપેલ એરેમાં એક બીજાથી k અંતરની અંદર ડુપ્લિકેટ તત્વો છે કે કેમ તે તપાસો  


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે એમેઝોન અવલારા સિટાડેલ ફ્રીચાર્જ હેકરરંક Snapchat સ્નેપડીલ
અરે હેશ

સમસ્યા "તપાસો કે આપેલ એરે એક બીજાથી k અંતરની અંદર ડુપ્લિકેટ તત્વો ધરાવે છે કે કેમ" તે જણાવે છે કે આપણે k ની રેન્જમાં આપેલ અ unર્ડર્ડર્ડ એરેમાં ડુપ્લિકેટ્સ તપાસવી પડશે અહીં k ની વેલ્યુ આપેલ એરે કરતા ઓછી છે.

આપેલ એરેમાં એક બીજાથી k અંતરની અંદર ડુપ્લિકેટ તત્વો છે કે કેમ તે તપાસોપિન

ઉદાહરણો  

K = 3   arr[] = {1, 2, 3, 4, 5, 2, 1}
False
K = 2   arr[] = {3, 4, 3, 1, 1, 2, 6}
True

સમજૂતી

આ સમસ્યા હલ કરવા માટે અમારી પાસે બે પદ્ધતિઓ છે. એક સરળ એ બે લૂપ્સ ચલાવવું છે જેમાં પ્રથમ લૂપ દરેક તત્વને બીજા લૂપ 'આંતરિક લૂપ' માટે પ્રારંભિક તત્વ તરીકે પસંદ કરશે. તે પછી, બીજું લૂપ પ્રારંભિક તત્વની તુલના 'કે' ની અંદરના બધા તત્વો સાથે કરશે. પરંતુ આ સોલ્યુશન એટલું કાર્યક્ષમ નથી કે તે ઓ (કે * એન) ની સમય જટિલતા લે છે.

પરંતુ અમારી પાસે બીજી વધુ કાર્યક્ષમ પદ્ધતિ છે જે સમસ્યાને હલ કરી શકે છે ઓ (એન) સમય જટિલતા કહેવાય છે હેશીંગ. હેશીંગ પદ્ધતિમાં, આપણે એરેના બધા તત્વોને વટાવીશું અને અમે તપાસીશું કે તેમાં એલિમેન્ટ છે કે નહીં. જો એલિમેન્ટ ત્યાં છે તો આપણે 'ટ્રુ' પાછા આવીશું. બાકી આપણે તેને હેશમાં ઉમેરીશું અને હેશમાંથી એરર [ik] એલિમેન્ટને દૂર કરીશું જો 'i' 'k' કરતા વધારે અથવા તેના બરાબર છે.

આ પણ જુઓ
પત્ર કેસ પરમ્યુટેશન

અલ્ગોરિધમનો તપાસો કે આપેલ એરેમાં એક બીજાથી k અંતરની અંદર ડુપ્લિકેટ તત્વો છે કે કેમ  

  1. પ્રથમ, ખાલી બનાવો હેશ સેટ જેમાં આપણે એરેના તત્વો સંગ્રહિત કરીશું.
  2. એરેના બધા તત્વોને ડાબેથી જમણે પસાર કરો.
  3. તત્વ હેશમાં છે કે કેમ તે તપાસો.
    • જો તે ત્યાં છે તો પાછા "સાચા."
    • બાકી તે તત્વોને હેશમાં ઉમેરો.
  4. તે પછી એઆર [ik] એલિમેન્ટને હેશથી દૂર કરો જો 'હું' વધારે કે 'K' ની બરાબર છે.

 

આપણી પાસે એરે 'એરે []' છે જેમાં તેમાં કેટલાક એલિમેન્ટ છે અને વેલ્યુ કે જે રેન્જ છે જેમાં આપણે ડુપ્લિકેટ્સ શોધી કા toવી છે જો ત્યાં કોઈ તત્વો સંગ્રહવા માટે હેશ સેટનો ઉપયોગ કરીશું તો પહેલા આપણે તેમાં તત્વો ઉમેરીશું. અમારા હેશમાં એરે એક પછી એક સેટ કરે છે જો એલિમેન્ટ પહેલાથી હેશ સેટમાં હોય તો તે સાચું પાછું આવશે અને લૂપને તોડી નાખશે નહીં તો તે સેટમાં તત્વોને સતત દાખલ કરશે અને સેટમાંથી એઆર [ik] એલિમેન્ટને દૂર કરશે.

કોડ  

સી ++ કોડ તપાસવા માટે કે આપેલ એરે એક બીજાથી k અંતરની અંદર ડુપ્લિકેટ તત્વો ધરાવે છે કે કેમ

#include<iostream>
#include<unordered_set>
using namespace std;

bool Check_Duplicates(int a[], int n, int k)
{

    unordered_set<int> D_set;

    for (int i = 0; i < n; i++)
    {
        if (D_set.find(a[i]) != D_set.end())
            return true;

        D_set.insert(a[i]);
        if (i >= k)
            D_set.erase(a[i-k]);
    }
    return false;
}

int main ()
{
    int a[] = {1, 2, 3, 4, 1};
    int k = 5;
    cout << ((Check_Duplicates(a, 5, k)) ? "Yes" : "No");
}
Yes

જાવા કોડ એ તપાસવા માટે કે આપેલ એરેમાં એક બીજાથી k અંતરની અંદર ડુપ્લિકેટ તત્વો છે કે કેમ

import java.util.*;
class D_Class
{
    static boolean Check_Duplicates(int a[], int k)
    {

        HashSet<Integer> D_set = new HashSet<>();

        for (int i=0; i<a.length; i++)
        {
            if (D_set.contains(a[i]))
                return true;

            D_set.add(a[i]);
            if (i >= k)
                D_set.remove(a[i-k]);
        }
        return false;
    }

    public static void main (String[] args)
    {
        int a[] = {1, 2, 3, 4, 1};
        int k = 5;

        if (Check_Duplicates(a, k))
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}
Yes

જટિલતા વિશ્લેષણ  

સમય જટિલતા

ઓ (એન) જ્યાં “એન” એરેમાં તત્વોની સંખ્યા છે. હેશ સેટનો ઉપયોગ રેખીય સમયમાં સમસ્યા હલ કરવાની મંજૂરી આપે છે. હેશ સેટનો ઉપયોગ કરવાથી ડેટાને શોધવાની, કા deleteી નાખવાની અને અસરકારક રીતે દાખલ કરવાની ક્ષમતા વધારે છે.

આ પણ જુઓ
આપેલ ઉત્પાદન સાથે જોડી બનાવો

અવકાશ જટિલતા

બરાબર) જ્યાં “કે” વિંડોમાં તત્વોની સંખ્યા છે કે જેના પર ધ્યાન આપવું જરૂરી છે.