Պարունակում է կրկնօրինակ II Leetcode լուծում


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Amazon facebook Google
Դասավորություն Հեշինգ Սահող պատուհան

Խնդիրի հայտարարություն

Այս խնդրում մեզ տրվում է ան դասավորություն ամբողջ թվերի, և մենք պետք է ստուգենք, արդյոք գոյություն ունի որևէ կրկնօրինակ տարր, որը գտնվում է առնվազն հեռավորության վրա k իրար հանդեպ.
այսինքն `այդ երկու նույն տարրի ցուցիչների միջև տարբերությունը պետք է լինի k- ից հավասար:
Կամ,  nums [i] == nums [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 հեռավորությունից անմիջապես դրանից ՝ կա՞ որևէ տարր առկա է, թե ոչ:
Եթե ​​որևէ տարր հայտնաբերվում է ներկա տարրի հետ, ապա մենք ճիշտ ենք վերադառնում, հակառակ դեպքում կեղծ ենք վերադառնում:

Ալգորիթմ

  1. Գործարկեք օղակ յուրաքանչյուր տարրի համար nums [i] տրված զանգվածի.
  2. Այս օղակի ներսում կրկին գործարկեք for հանգույց և անցեք բոլոր տարրերից j = ես + 1 դեպի j = ես + կ և համեմատել դրա արժեքը nums [i]:
    • If nums [j] == nums [i] ապա վերադարձիր ճշմարիտ: Քանի որ մենք գտել ենք մի տարր:
  3. Վերջապես, երբ կրկնօրինակ տարր չի հայտնաբերվում, ապա գործառույթից դուրս գալուց առաջ կեղծ վերադարձեք:

Իրականացումը պարունակում է Duplicate 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

Բարդության վերլուծություն պարունակում է Duplicate II Leetcode լուծում

Timeամանակի բարդություն

O (n * min (k, n)): Մենք անցնում ենք min (k, n) տարրեր զանգվածի յուրաքանչյուր տարրի համար: Ուստի ժամանակի բարդությունը կլինի O (n * min (k, n)):

Տիեզերական բարդություն 

O (1): Մշտական ​​տարածություն:

Մոտեցում 2 (լոգարիթմական պատուհան)

Ինչպես տեսնում ենք, մենք մեկից ավելի անգամ ենք գնում զանգվածի տարրերին, ինչը մեծացնում է դրա ժամանակի բարդությունը: Մենք պետք է միայն մեկ անգամ այցելենք յուրաքանչյուր տարր `O (n) ժամանակը կրճատելու համար:

Դրա համար այն, ինչ կարող ենք անել, այն է, որ կարողանանք պահել նախորդի լոգարիթմական պատուհանը k տարրեր, օգտագործելով Hash Set ամեն անգամ, երբ այցելում ենք զանգվածի ցանկացած տարր: Դրանով մենք կարող ենք հեշտությամբ ստուգել նախորդ k տարրերի հավաքածուից, արդյոք հավաքածուի մեջ կա մի տարր, որը նույնն է ներկայիս տարրին, որը մենք այցելում ենք: Եթե ​​մենք գտել ենք մեկում հավաքածուի մեջ, ապա այդ պահին մենք վերադառնանք իրական: Այլապես մենք հավաքածուի մեջ կներդնենք ընթացիկ տարրը և հավաքածուից կհեռացնենք նաև վերջին այցելած տարրը, որպեսզի միշտ ունենանք k նախորդ տարրերը մեր հավաքածուի մեջ:

Տեսնենք ստորև նկարում բերված մի օրինակ.

Պարունակում է կրկնօրինակ II Leetcode լուծում

Ալգորիթմ

  1. Ստեղծել Հեշ հավաքածու պահելու համար k նախորդ տարրերը:
  2. Անցում տրված զանգվածի համարների [i] յուրաքանչյուր տարրի համար օղակում:
    • Ստուգեք ՝ արդյոք հաշի հավաքածուն արդեն պարունակում է [i] համարներ, թե ոչ: Եթե ​​թվերը [i] առկա են հավաքածուում (այսինքն ՝ կրկնօրինակ տարրը առկա է հավասար հավասարից պակաս հեռավորության վրա) k ), ապա վերադառնալ ճշմարիտ: Ուրիշները թվին ավելացրու [i] լրակազմին:
    • Եթե ​​բազմության չափը մեծ է k- ից, ապա հավաքածուից հեռացրեք վերջին այցելած տարրը (nums [ik]):
  3. Վերջապես, երբ կրկնօրինակ տարր չի հայտնաբերվում, ապա գործառույթից դուրս գալուց առաջ կեղծ վերադարձեք:

Իրականացումը պարունակում է Duplicate 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

Բարդության վերլուծություն պարունակում է Duplicate II Leetcode լուծում

Timeամանակի բարդություն

Վրա) : Քանի որ մենք այցելում ենք յուրաքանչյուր տարր միայն մեկ անգամ և ենթադրելով, որ տարր ավելացնելը և տարրը հեռացնելը տևում է անընդհատ ժամանակ `հեշ ժամանակի ժամանակի բարդությունը, որը կրճատվում է մինչև O (n):

Տիեզերական բարդություն 

O (min (k, n)): Մենք պահում ենք k տարրեր առավելագույնը հեշ հավաքածուում: Եթե ​​k> n ապա հավաքածուում կպահպանվի միայն n տարրը առավելագույնը: