የተባዛ II ሌቲኮድ መፍትሄን ይል


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ አማዞን ፌስቡክ google
ሰልፍ ሃምሽንግ የተንሸራታች መስኮት

የችግሩ መግለጫ

በዚህ ችግር ውስጥ አንድ ተሰጠን ደርድር የቁጥር ቁጥሮች እና ቢያንስ አንድ ርቀት ላይ ያሉ የተባዙ አባሎች ካሉ ማረጋገጥ አለብን k ለ እርስበርስ.
ማለትም በእነዚያ ሁለት ተመሳሳይ ንጥረ ነገሮች ጠቋሚዎች መካከል ያለው ልዩነት ከ k ጋር እኩል መሆን አለበት ፡፡
አሁን  ቁጥሮች [i] == ቁጥሮች [j] abs (ij) <= ኪ

ለምሳሌ

nums = [1,2,3,1], k = 3
true

ማብራሪያ:

በመረጃ ጠቋሚ 0 እና 3 ላይ ያለው ንጥረ ነገር ተመሳሳይ ነው ፣ እና 3 - 0 <= k.

nums = [1,2,3,1,2,3], k = 2
false

አቀራረብ 1 (የጭካኔ ኃይል)

ስለ ጭካኔ ኃይል አቀራረብ ከተነጋገርን በቀላሉ ሁለት ቀለበቶችን በመጠቀም መርሃግብሩን ተግባራዊ ማድረግ እና የአሁን ንጥረ ነገር መኖሩ ወይም አለመኖሩ ከየትኛውም የድርድር ክፍል ርቀቱን በትክክል ማረጋገጥ እንችላለን ፡፡
ማንኛውም ንጥረ ነገር ከአሁኑ ንጥረ ነገር ጋር ተመሳሳይ ሆኖ ከተገኘ ከዚያ ወደ እውነት እንመለሳለን አለበለዚያ ሐሰተኛ እንሆናለን ፡፡

አልጎሪዝም

  1. ለእያንዳንዱ ንጥረ ነገር አንድ ዙር ያሂዱ ቁጥሮች [i] የተሰጠው ድርድር።
  2. በዚህ ዑደት ውስጥ እንደገና ለሉፕ አንድ አሂድ እና ሁሉንም ንጥረ ነገሮች ከየት ይለፍ j = i + 1 ወደ j = i + k እና እሴቱን ከ ቁጥሮች [እኔ]።
    • If ቁጥሮች [j] == ቁጥሮች [i] ከዚያ ወደ እውነት ተመለሱ ፡፡ አንድ ንጥረ ነገር እንዳገኘነው ፡፡
  3. በመጨረሻም ምንም የተባዛ ንጥረ ነገር በማይገኝበት ጊዜ ተግባሩን ከመውጣቱ በፊት ወደ ሐሰት መመለስ ፡፡

ትግበራ የተባዛ II ሌትኮድ መፍትሄን ይ Conል

C ++ ፕሮግራም

#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 የ Leetcode መፍትሄን ይ Conል

የጊዜ ውስብስብነት

ኦ (n * ደቂቃ (k, n)) ለእያንዳንዱ የድርድር አካል ደቂቃ (k, n) አባሎችን እየተጓዝን ነው። ስለዚህ የጊዜ ውስብስብነት O (n * min (k, n)) ይሆናል።

የቦታ ውስብስብነት 

ኦ (1) ቋሚ ቦታ.

አቀራረብ 2 (ተንሸራታች መስኮት)

እንደምናየው ከአንድ በላይ ጊዜዎች ወደ ውስጡ ውስብስብነት የሚጨምር ወደ ድርድሩ አካላት እንሄዳለን ፡፡ ጊዜውን ወደ O (n) ለመቀነስ ወደ እያንዳንዱ አካል አንድ ጊዜ ብቻ መጎብኘት አለብን ፡፡

ለዚያ እኛ ማድረግ የምንችለው የቀደመውን ተንሸራታች መስኮት ማቆየት እንችላለን k የ ‹Hash› ን ስብስብ የሚጠቀሙ ንጥረ ነገሮች ማንኛውንም የድርድርን ማንኛውንም ክፍል ስንጎበኝ ፡፡ ይህንን በማድረጋችን አሁን ከጎበኘነው የአሁኑ ንጥረ ነገር ጋር ተመሳሳይ የሆነ ንጥረ ነገር ካለ በስብስቡ ውስጥ ካለ ከቀደሙት k አባሎች ስብስብ በቀላሉ መመርመር እንችላለን ፡፡ በተዘጋጀ አንድ ካገኘን በዚያን ጊዜ በእውነቱ እንመለሳለን ፡፡ አለበለዚያ እኛ የአሁኑን ንጥረ ነገር በስብስቡ ውስጥ እናስገባለን እንዲሁም የመጨረሻውን የተጎበኘውን ንጥረ ነገር እኛ ሁልጊዜ እንዲኖረን ከስብስቡ ውስጥ እናስወግደዋለን k ቀዳሚ አባሎች በእኛ ስብስብ ውስጥ።

ከዚህ በታች በምስል ላይ አንድ ምሳሌ እንመልከት

የተባዛ II ሌቲኮድ መፍትሄን ይል

አልጎሪዝም

  1. ፍጠር የሃሽ ስብስብ ለማከማቸት k ቀዳሚ አካላት.
  2. በክብ ውስጥ ለተሰጠው ድርድር ለእያንዳንዱ አባል ቁጥሮች [i] ተጓዥ።
    • የሃሽ ስብስብ ቀድሞ ቁጥሮች (i) ካለ ወይም እንዳልሆነ ያረጋግጡ። ቁጥሮች (i) በተቀመጠው ውስጥ ካሉ (ማለትም የተባዛ አካል ከእኩል በታች በሆነ ርቀት ይገኛል) k ) ፣ ከዚያ ወደ እውነት ይመለሱ። ሌላ ቁጥሮችን [i] ን ወደ ስብስቡ ያክሉ።
    • የስብስብ መጠን ከ k የሚበልጥ ከሆነ የመጨረሻውን የጎበኘውን ንጥረ ነገር (nums [ik]) ከስብስቡ ውስጥ ያስወግዱ።
  3. በመጨረሻም ምንም የተባዛ ንጥረ ነገር በማይገኝበት ጊዜ ተግባሩን ከመውጣቱ በፊት ወደ ሐሰት መመለስ ፡፡

ትግበራ የተባዛ II ሌትኮድ መፍትሄን ይ Conል

C ++ ፕሮግራም

#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 የ Leetcode መፍትሄን ይ Conል

የጊዜ ውስብስብነት

ኦ (n): እያንዳንዱን ንጥረ ነገር አንድ ጊዜ ብቻ እንደጎበኘን እና አንድ ንጥረ ነገር ማከል እና አንድን ንጥረ ነገር ማስወገድ በ O (n) ብቻ የተቀነሰ በሃሽ ጊዜ ውስጥ ውስብስብነት ውስጥ የማያቋርጥ ጊዜ ይወስዳል ፡፡

የቦታ ውስብስብነት 

ኦ (ደቂቃ (ኬ ፣ n)) እኛ ሃሽ ስብስብ ውስጥ ቢበዛ k አባሎችን እያከማቸን ነው ፡፡ ከሆነ k> n ከዚያ n ብቻ ኤለመንት በከፍተኛው ስብስብ ውስጥ ይቀመጣል ፡፡