අනුපිටපත් 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 සිට දුරින් 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)): අපි අරාවෙහි සෑම මූලද්‍රව්‍යයක් සඳහාම මිනි (k, n) මූලද්‍රව්‍ය හරහා ගමන් කරන්නෙමු. එබැවින් කාල සංකීර්ණතාව O (n * min (k, n)) වේ.

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

ඕ (1): නිරන්තර අවකාශය.

ප්‍රවේශය 2 (ස්ලයිඩින් කවුළුව)

අපට පෙනෙන පරිදි, අපි අරාවෙහි මූලද්‍රව්‍ය වෙත එක් වරකට වඩා වැඩි කාලයක් යන අතර එමඟින් එහි කාල සංකීර්ණතාව වැඩි වේ. O (n) දක්වා කාලය අඩු කිරීම සඳහා අප එක් එක් මූලද්‍රව්‍යයට එක් වරක් පමණක් පිවිසිය යුතුය.

ඒ සඳහා අපට කළ හැක්කේ අපට පෙර ස්ලයිඩින් කවුළුවක් තබා ගත හැකිය k අපි අරාවෙහි ඕනෑම අංගයකට පිවිසෙන සෑම අවස්ථාවකම හැෂ් කට්ටලයක් භාවිතා කරන අංග. මෙය සිදු කිරීමෙන්, අප සංචාරය කරන වර්තමාන මූලද්‍රව්‍යයට සමාන මූලද්‍රව්‍යයක් කට්ටලයේ තිබේදැයි අපට පෙර k මූලද්‍රව්‍ය කට්ටලයෙන් පහසුවෙන් පරීක්ෂා කළ හැකිය. අපි එකක් සෙට් එකක් සොයා ගත්තා නම්, ඒ මොහොතේදී අපි සත්‍යය වෙත ආපසු යමු. නැතහොත් අපි කට්ටලයේ වත්මන් මූලද්‍රව්‍යය ඇතුළු කර අවසන් වරට පිවිසුණු මූලද්‍රව්‍යය කට්ටලයෙන් ඉවත් කරන්නෙමු k අපගේ කට්ටලයේ පෙර අංග.

පහත රූපයේ උදාහරණයක් බලමු:

අනුපිටපත් 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 (min (k, n)): අපි හැෂ් කට්ටලයේ උපරිම වශයෙන් k මූලද්‍රව්‍ය ගබඩා කරමු. K> n නම් උපරිම වශයෙන් කට්ටලය තුළ n මූලද්‍රව්‍යය පමණක් ගබඩා වේ.