දී ඇති අරාවෙහි එකිනෙකට k දුරින් අනුපිටපත් මූලද්‍රව්‍ය අඩංගු දැයි පරීක්ෂා කරන්න


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ ඇමේසන් අවලාරා සිටඩෙල් FreeCharge හැකර් රැන්ක් Snapchat Snapdeal
අරා හැෂ්

“දී ඇති අරාවෙහි එකිනෙකට k දුරින් අනුපිටපත් මූලද්‍රව්‍ය තිබේදැයි පරීක්ෂා කරන්න” යන ගැටළුවෙහි දැක්වෙන්නේ, k පරාසය තුළ ලබා දී ඇති අනුපිළිවෙලට නැති අරාවෙහි අනුපිටපත් සඳහා අප පරීක්ෂා කළ යුතු බවයි. මෙහි k හි අගය දී ඇති අරාවට වඩා කුඩා වේ.

දී ඇති අරාවෙහි එකිනෙකට k දුරින් අනුපිටපත් මූලද්‍රව්‍ය අඩංගු දැයි පරීක්ෂා කරන්න

උදාහරණ

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

පැහැදිලි කිරීම

මෙම ගැටළුව විසඳීම සඳහා අපට ක්‍රම දෙකක් තිබේ. සරලම දෙය නම් පළමු ලූපය සෑම අංගයක්ම ආරම්භක අංගයක් ලෙස දෙවන ලූපය 'ඉනර් ලූප්' සඳහා තෝරා ගන්නා ලූප දෙකක් ධාවනය කිරීමයි. ඊට පසු, දෙවන ලූපය ආරම්භක මූලද්‍රව්‍යය 'k' පරාසය තුළ ඇති සියලුම මූලද්‍රව්‍ය සමඟ සංසන්දනය කරනු ඇත. නමුත් මෙම විසඳුම එතරම් කාර්යක්ෂම නොවන බැවින් O (k * n) හි සංකීර්ණත්වය අවශ්‍ය වේ.

නමුත් අපට තවත් කාර්යක්ෂම ක්‍රමයක් ඇති අතර එමඟින් ගැටළුව විසඳා ගත හැකිය සාමාන්ය (n) කාල සංකීර්ණත්වය හැඳින්වේ හැෂිං. හැෂිං ක්‍රමයේදී, අපි අරාවෙහි සියලුම අංග හරහා ගමන් කරන අතර මූලද්‍රව්‍යය එහි තිබේද නැද්ද යන්න පරීක්ෂා කර බලමු. මූලද්රව්යය එහි තිබේ නම් අපි 'ඇත්ත' නැවත ලබා දෙන්නෙමු. නැතහොත් අපි එය හැෂ් එකට එකතු කර 'i' 'k' ට වඩා විශාල හෝ සමාන නම් හැෂ් වෙතින් අර [ik] මූලද්‍රව්‍යය ඉවත් කරමු.

ලබා දී ඇති අරාවෙහි එකිනෙකට k දුරින් අනුපිටපත් මූලද්‍රව්‍ය තිබේදැයි පරීක්ෂා කිරීමට ඇල්ගොරිතම

  1. පළමුව, හිස් නිර්මාණය කරන්න හැෂ් කට්ටලය එහිදී අපි අරාවෙහි මූලද්‍රව්‍ය ගබඩා කරමු.
  2. අරාවේ සියලුම අංග වමේ සිට දකුණට ගමන් කරන්න.
  3. මූලද්‍රව්‍යය හැෂ් තුළ තිබේද නැද්ද යන්න පරීක්ෂා කරන්න.
    • එය එහි තිබේ නම් “සත්‍ය” වෙත ආපසු යන්න.
    • නැතිනම් එම මූලද්‍රව්‍යය හැෂ් එකට එක් කරන්න.
  4. ඊට පසු 'I' 'k' ට වඩා විශාල හෝ සමාන නම් හැෂ් වෙතින් අර [ik] මූලද්‍රව්‍යය ඉවත් කරන්න.

 

අපට අරාවෙහි 'අර [ අපගේ හැෂ් කට්ටලයේ අරාව එකින් එක සකසා තිබේ නම් මූලද්‍රව්‍යය දැනටමත් හැෂ් කට්ටලයේ තිබේ නම් එය සත්‍ය බවට පත්වී ලූපය බිඳ දමනු ඇත.

කේතය

ලබා දී ඇති අරාවෙහි එකිනෙකට k දුරින් අනුපිටපත් මූලද්‍රව්‍ය තිබේද යන්න පරීක්ෂා කිරීමට C ++ කේතය

#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

සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණත්වය

සාමාන්ය (n) එහිදී “N” යනු අරාවෙහි ඇති මූලද්‍රව්‍ය ගණන වේ. හැෂ් කට්ටලයක් භාවිතා කිරීමෙන් ගැටළුව රේඛීය වේලාවට විසඳීමට ඉඩ ලබා දේ. හැෂ් කට්ටලය භාවිතා කිරීමෙන් දත්ත කාර්යක්ෂමව සෙවීමට, මකා දැමීමට සහ ඇතුළු කිරීමේ හැකියාව වැඩි කරයි.

අභ්‍යවකාශ සංකීර්ණතාව

හරි) එහිදී “K” යනු කවුළුව තුළ සොයා බැලිය යුතු මූලද්‍රව්‍ය ගණන වේ.