Leetcode II кайталанма чечимин камтыйт


Кыйынчылык деңгээли жеңил
Көп суралган Amazon Facebook Гугл
согуштук тизме Hashing Жылма терезе

Маселени билдирүү

Бул маселеде бизге согуштук тизме бүтүндөй сандар жана биз жок дегенде аралыкта кайталанган элементтин бар экендигин текшеришибиз керек k бири бирине.
б.а. ошол эки элементтин индекстеринин айырмасы kга барабар болбошу керек.
же болбосо,  nums [i] == nums [j] жана abs (ij) <= k

мисал

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

Explanation:

0 жана 3 индексиндеги элемент бирдей, ал эми 3 - 0 <= k.

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

Approach 1 (Brute Force)

Эгерде биз орой күч колдонуу ыкмасы жөнүндө айта турган болсок, анда эки циклди колдонуп, программанын ар бир элементин андан оңго карай k аралыкта текшерип, кандайдыр бир элемент бар же жок экендигин текшерсек болот.
Эгерде кандайдыр бир элемент учурдагы элементке окшош болсо, анда биз true деп кайтарабыз, антпесе жалган деп кайтарабыз.

Algorithm

  1. Ар бир элемент үчүн цикл иштетүү nums [i] берилген массивдин
  2. Ушул циклдин ичинде кайрадан for for циклин иштетип, бардык элементтерди аралап өтүңүз j = i + 1 үчүн j = i + k жана анын маанисин менен салыштырыңыз nums [i].
    • If nums [j] == nums [i] анда чыныгы кайтып. Биз бир элемент таптык эле.
  3. Акыр-аягы, эч кандай кайталануучу элемент табылбай калганда, функциядан чыкканга чейин false дегенди кайтарыңыз.

II Leetcode Чечиминин Дубликатын камтыйт

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

Java программасы

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 Чечиминин Кайталанма Чечими камтылган Комплекстик Анализ

Убакыт татаалдыгы

O (n * min (k, n)): Массивдин ар бир элементи үчүн min (k, n) элементтерин аралап жатабыз. Демек, убакыттын татаалдыгы O (n * min (k, n)) болот.

Космостун татаалдыгы 

O (1): Туруктуу мейкиндик.

2-ыкма (Жылма терезе)

Көрүнүп тургандай, массивдин элементтерине бир нече жолу барып жатабыз, бул анын убакыттын татаалдыгын жогорулатат. Убакытты O (n) чейин кыскартуу үчүн ар бир элементке бир гана жолу барышыбыз керек.

Ал үчүн биз мурунку терезени жылдырсак болот k Массивдин каалаган элементтерине барган сайын Hash Setти колдонгон элементтер. Муну менен биз мурунку k элементтердин жыйындысынан оңой эле текшерип алабыз, эгерде бул жыйында биз барган учурдагы элемент менен бирдей элемент бар болсо. Эгерде биз комплекттен бирөөсүн тапсак, анда ошол учурда биз чындыгында кайтып келебиз. Башка учурларда, биз учурдагы элементти комплектке киргизип, ошондой эле акыркы барган элементти ар дайым алып турабыз k мурунку элементтери.

Төмөндөгү сүрөттөгү мисалды карап көрөлү:

Leetcode II кайталанма чечимин камтыйт

Algorithm

  1. түзүү Hash Set сактоо үчүн k мурунку элементтер.
  2. Берилген массивдин циклдериндеги [i] ар бир элемент үчүн өтүү.
    • Хэш топтомунда [i] сандары бар же жок экендигин текшериңиз. Эгерде жыйнакта nums [i] бар болсо (б.а. кайталанган элемент барабар болбогон аралыкта болот k ), андан кийин true кайтып келет. Башка саны [i] топтомго кошулат.
    • Эгерде топтомдун көлөмү k дан чоң болсо, анда акыркы кирген элементти (nums [ik]) топтомдон алып салыңыз.
  3. Акыр-аягы, эч кандай кайталануучу элемент табылбай калганда, функциядан чыкканга чейин false дегенди кайтарыңыз.

II Leetcode Чечиминин Дубликатын камтыйт

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

Java программасы

#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 Чечиминин Кайталанма Чечими камтылган Комплекстик Анализ

Убакыт татаалдыгы

O (n): Ар бир элементке бир жолу гана барып, элементти кошуу жана элементти алып салуу O (n) га чейин кыскарган хэш белгиленген убакыттын татаалдыгында туруктуу убакытты талап кылат деп эсептесек.

Космостун татаалдыгы 

O (min (k, n)): Биз k элементтерин таштанды топтомунда максималдуу деңгээлде сактап жатабыз. Эгерде k> n болсо, анда n элемент гана эң көп дегенде топтомдо сакталат.