შეამოწმეთ, მოცემული მასივი შეიცავს თუ არა დუბლიკატ ელემენტებს ერთმანეთისგან k მანძილზე


Რთული ტური Easy
ხშირად ეკითხებიან Amazon ავალარა ციხედ უფასო დატენვა HackerRank Snapchat Snapdeal
Array Hash

პრობლემა "შეამოწმეთ მოცემული მასივი შეიცავს თუ არა დუბლიკატ ელემენტებს k ერთმანეთისგან დაშორებით" აცხადებს, რომ ჩვენ უნდა გადავამოწმოთ დუბლიკატები მოცემულ არაორგანიზებულ მასივში k დიაპაზონში. აქ k –ს მნიშვნელობა ნაკლებია მოცემულ მასივზე.

შეამოწმეთ, მოცემული მასივი შეიცავს თუ არა დუბლიკატ ელემენტებს ერთმანეთისგან k მანძილზე

მაგალითები

K = 3   arr[] = {1, 2, 3, 4, 5, 2, 1}
False
K = 2   arr[] = {3, 4, 3, 1, 1, 2, 6}
True

განმარტება

ჩვენ ამ პრობლემის გადაჭრის ორი მეთოდი გვაქვს. უმარტივესია ორი მარყუჟის გაშვება, რომელშიც პირველი მარყუჟი აირჩევს ყველა ელემენტს, როგორც საწყისი ელემენტი მეორე მარყუჟის "შიდა მარყუჟის "თვის. ამის შემდეგ, მეორე ციკლი შეადარებს საწყისი ელემენტს და ყველა ელემენტს 'k' - ის დიაპაზონში. მაგრამ ეს გამოსავალი არც ისე ეფექტურია, სჭირდება O (k * n) სირთულე.

მაგრამ ჩვენ გვაქვს კიდევ ერთი უფრო ეფექტური მეთოდი, რომელსაც პრობლემის გადაჭრა შეუძლია O (n) დროის სირთულე ე.წ. ჰასინგი. ჰეშირების მეთოდით, ჩვენ გადავხედავთ მასივის ყველა ელემენტს და შეამოწმებთ არის თუ არა ელემენტი მასში. თუ ელემენტი იქ არის, ჩვენ დავუბრუნებთ "True" - ს. სხვაგვარად, ჩვენ მას დავამატებთ ჰეშს და მოვაცილებთ arr [ik] ელემენტს ჰაშიდან, თუ 'i' მეტია ან ტოლია 'k'.

ალგორითმის შემოწმება, მოცემული მასივი შეიცავს თუ არა დუბლიკატ ელემენტებს ერთმანეთისგან k მანძილზე

  1. პირველი, შექმნა ცარიელი ჰეშების ნაკრები რომელშიც ჩვენ ვინახავთ მასივის ელემენტებს.
  2. მასივის ყველა ელემენტის გადაკვეთა მარცხნიდან მარჯვნივ.
  3. შეამოწმეთ, ელემენტია თუ არა ჰაში.
    • თუ ის იქ არის, მაშინ დააბრუნე "ჭეშმარიტი".
    • სხვა დაამატეთ ეს ელემენტი ჰეშს.
  4. ამის შემდეგ ამოიღეთ arr [ik] ელემენტი ჰაშიდან, თუ 'I' მეტია ან ტოლია 'k'.

 

ჩვენ გვაქვს მასივი 'arr []', რომელშიც არის გარკვეული ელემენტი და მნიშვნელობა k, რომელიც არის დიაპაზონი, სადაც უნდა ვიპოვოთ დუბლიკატები, თუ არსებობს, ასე რომ, გამოიყენეთ hash set მასში ელემენტების შესანახად, პირველ რიგში დავამატებთ ელემენტებს მასივი ჩვენს ჰაში ნაკრებში სათითაოდ თუ ელემენტი უკვე ჰეშების ნაკრებშია, მაშინ ის დაბრუნდება true და გამოყოფს მარყუჟს, სხვაგან ის მუდმივად ჩასვამს ელემენტებს სიმრავლეში და ამოიღებს arr [ik] ელემენტს სიმრავლიდან.

კოდი

C ++ კოდი, რათა შეამოწმოთ მოცემული მასივი შეიცავს თუ არა დუბლიკატ ელემენტებს ერთმანეთისგან k მანძილზე

#include<iostream>
#include<unordered_set>
using namespace std;

bool Check_Duplicates(int a[], int n, int k)
{

    unordered_set<int> D_set;

    for (int i = 0; i < n; i++)
    {
        if (D_set.find(a[i]) != D_set.end())
            return true;

        D_set.insert(a[i]);
        if (i >= k)
            D_set.erase(a[i-k]);
    }
    return false;
}

int main ()
{
    int a[] = {1, 2, 3, 4, 1};
    int k = 5;
    cout << ((Check_Duplicates(a, 5, k)) ? "Yes" : "No");
}
Yes

ჯავის კოდი, რათა შეამოწმოს, მოცემული მასივი შეიცავს თუ არა დუბლიკატ ელემენტებს ერთმანეთისგან k მანძილზე

import java.util.*;
class D_Class
{
    static boolean Check_Duplicates(int a[], int k)
    {

        HashSet<Integer> D_set = new HashSet<>();

        for (int i=0; i<a.length; i++)
        {
            if (D_set.contains(a[i]))
                return true;

            D_set.add(a[i]);
            if (i >= k)
                D_set.remove(a[i-k]);
        }
        return false;
    }

    public static void main (String[] args)
    {
        int a[] = {1, 2, 3, 4, 1};
        int k = 5;

        if (Check_Duplicates(a, k))
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}
Yes

სირთულის ანალიზი

დროის სირთულე

O (n) სადაც "ნ" არის მასივის ელემენტების რაოდენობა. Hash Set– ის გამოყენება საშუალებას იძლევა პრობლემის გადაჭრას წრფივ დროში. ვინაიდან ჰეშ – ნაკრების გამოყენება ზრდის მონაცემთა ეფექტურად ძიების, წაშლისა და ჩასმის შესაძლებლობას.

სივრცის სირთულე

Კარგი) სადაც "K" არის ფანჯარაში არსებული ელემენტების რაოდენობა, რომელთა დათვალიერებაა საჭირო.