Санҷед, ки оё массиви додашуда унсурҳои такрориро дар масофаи k аз ҳамдигар дар бар мегирад  


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад Amazon Авалара Citadel FreeCharge HackerRank Snapchat Snapdeal
тартиботи ҳарбӣ Хаш

Масъалаи "Санҷед, ки оё массиви додашуда унсурҳои такрориро дар масофаи 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) -и вақтро талаб мекунад.

Аммо мо як усули дигари самарабахше дорем, ки метавонад мушкилотро ҳал кунад Эй (н) мураккабии вақт номида мешавад тарошидан. Дар усули хэшкунӣ, мо ҳамаи унсурҳои массивро убур карда, месанҷем, ки оё он дар он мавҷуд аст ё не. Агар унсур дар он ҷо бошад, пас мо 'True' -ро бармегардонем. Дар акси ҳол, мо онро ба хэш илова карда, унсури arr [ik] -ро аз ҳаш хориҷ мекунем, агар 'i' аз 'k' зиёд ё ба он баробар бошад.

ҳамчунин нигаред
Иваз кардани парвандаи ҳарф

Алгоритми тафтиш, ки оё массиви додашуда унсурҳои такрориро дар масофаи k аз ҳамдигар дарбар мегирад ё не  

  1. Аввалан, холиро эҷод кунед шудаи таъин шудааст ки дар он мо унсурҳои массивро нигоҳ медорем.
  2. Тамоми элементҳои массивро аз чап ба рост убур кунед.
  3. Санҷед, ки оё ин элемент дар хэш мавҷуд аст ё не.
    • Агар дар он ҷо бошад, пас "true" -ро баргардонед.
    • Дигар ин унсурро ба хэш илова кунед.
  4. Пас аз он, унсури arr [ik] -ро аз hash хориҷ кунед, агар 'I' ба 'k' калон ё баробар бошад.

 

Мо массиви 'arr []' дорем, ки дар он баъзе унсурҳо мавҷуданд ва арзиши k, ки диапазонест, ки дар он мо бояд нусхаҳоро пайдо кунем, агар чунин бошад, барои нигоҳ доштани унсурҳо дар он аввал ҳаш маҷмӯаро истифода мебарем, аввал унсурҳои массиви ҳаштаи мо як ба як, агар элемент аллакай дар маҷмӯи хэш бошад, он гоҳ ҳақиқӣ бармегардад ва давраро мешиканад, он гоҳ элементҳоро ба маҷмӯъ пайваста дохил мекунад ва унсури 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

Рамзи Java барои Санҷед, ки оё массиви додашуда унсурҳои такрориро дар масофаи 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

Таҳлили мураккабӣ  

Мураккабии вақт

Эй (н) ки дар "Н" шумораи унсурҳои массив аст. Истифодаи Hash Set имкон медиҳад, ки масъала дар вақти хаттӣ ҳал карда шавад. Азбаски истифодаи маҷмӯи хэш қобилияти самаранок ҷустуҷӯ, нест кардан ва ворид кардани маълумотро тақвият медиҳад.

ҳамчунин нигаред
Бо маҳсулоти додашуда ҷуфт кунед

Мураккабии фазо

Хуб) ки дар "К" шумораи унсурҳои равзана аст, ки бояд онҳоро дида бароем.