Содржи Дупликат II решение за леткод


Ниво на тешкотија Лесно
Често прашувано во Амазон Facebook Google
Низа Хашинг Лизгачки прозорец

Изјава за проблем

Во овој проблем ни е дадена ан низа на цели броеви и мора да провериме дали има дупликат елемент што се наоѓа на најмалку растојание k еден на друг.
односно разликата помеѓу индексите на тие два исти елементи треба да биде помала од еднаква на k.
Или,  nums [i] == nums [j] апс (иј) <= 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 точно од него, дали има присутен елемент или не.
Ако кој било елемент се најде ист со тековниот, тогаш се враќаме точно, во спротивно се враќаме неточно.

Алгоритам

  1. Извршете јамка за секој елемент nums [i] на дадената низа.
  2. Внатре во оваа јамка повторно стартувајте јамка за и преминете ги сите елементи од j = јас + 1 до j = i + k и споредете ја нејзината вредност со nums [i].
    • If nums [j] == nums [i] тогаш врати се вистинити. Како што откривме елемент.
  3. Конечно, кога не се најде дупликат елемент, тогаш вратете неточно пред да излезете од функцијата.

Имплементација за содржи Дупликат II решение за леткод

Програма 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 решение за леткод

Временска комплексност

О (n * мин (k, n)): Прелистуваме мин (k, n) елементи за секој елемент од низата. Оттука, сложеноста на времето ќе биде O (n * min (k, n)).

Комплексноста на просторот 

О (1): Постојан простор.

Пристап 2 (Лизгачки прозорец)

Како што можеме да видиме, одиме повеќе од едно време до елементите на низата што ја зголемува неговата временска сложеност. Треба да го посетиме само еднаш секој елемент за да го намалиме времето до O (n).

За тоа, она што можеме да го направиме е да можеме да задржиме лизгачки прозорец од претходниот k елементи користејќи Hash Set секој пат кога посетуваме кој било елемент од низата. Со тоа можеме лесно да провериме од множеството на претходни k елементи дали постои елемент во множеството што е ист како тековниот елемент што го посетуваме. Ако пронајдовме еден во собата, тогаш во тој момент се враќаме вистинито. Друго, ќе го вметнеме тековниот елемент во множеството и исто така ќе го отстраниме последно посетениот елемент од множеството, така што секогаш го имаме k претходни елементи во нашиот сет.

Ајде да видиме пример на сликата подолу:

Содржи Дупликат II решение за леткод

Алгоритам

  1. Креирај Сет за хаш за чување k претходни елементи.
  2. Попречно за секој елемент, броеви [i] од дадената низа во јамка.
    • Проверете дали поставената хаш веќе содржи броеви [i] или не. Ако броевите [i] се присутни во множеството (т.е. дупликат елемент е присутен на растојание помало од еднакво на k ), а потоа вратете се вистинито. Друго, додадете броеви [i] во множеството.
    • Ако големината на множеството стане поголема од k, отстранете го последниот посетен елемент (nums [ik]) од множеството.
  3. Конечно, кога не се најде дупликат елемент, тогаш вратете неточно пред да излезете од функцијата.

Имплементација за содржи Дупликат II решение за леткод

Програма 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 решение за леткод

Временска комплексност

На) : Како што го посетуваме секој елемент само еднаш и претпоставувајќи дека додавањето на елемент и отстранувањето на елемент трае постојано време во сложеноста на времето за поставување хаш, намалена на само O (n).

Комплексноста на просторот 

О (мин (к, н)): Ние чуваме k елементи максимум во сетот хаш. Ако k> n тогаш само n елемент ќе биде зачуван во множеството максимум.