Берилген массивде бири-биринен k алыстыкта ​​кайталанган элементтердин бар экендигин текшерүү  


Кыйынчылык деңгээли жеңил
Көп суралган Amazon Avalara Citadel FreeCharge HackerRank снэпчат 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) талап кылат.

Бирок бизде көйгөйдү чече турган дагы бир натыйжалуу ыкма бар O (N) убакыт татаалдыгы деп аталат Хеширлөө. Хеширлөө ыкмасында, биз массивдин бардык элементтерин аралап, анын ичинде элементтин бар же жок экендигин текшеребиз. Эгер элемент ошол жерде болсо, анда биз "Чындыкты" кайтарабыз. Башка учурда биз аны таштоого кошобуз жана arr [ik] элементин таштандыдан алып салабыз, эгер 'i' 'k' дан чоң же ага барабар болсо.

ошондой эле
Letter Case Permutation

Берилген массивде бири-биринен k аралыкта кайталанма элементтер бар экендигин текшерүү алгоритми  

  1. Биринчиден, бошту жаратыңыз таштанды топтому анда биз массивдин элементтерин сактайбыз.
  2. Массивдин бардык элементтерин солдон оңго карай өтүңүз.
  3. Элементтин таштандында бар же жок экендигин текшериңиз.
    • Эгер ал жакта болсо, анда "true" деп кайрылыңыз.
    • Башка нерсе бул элементти таштандыга кошот.
  4. Андан кийин arr [ik] элементин таштандыдан чыгарыңыз, эгерде "I" "k" га чоң же барабар болсо.

 

Бизде кээ бир элементтери бар 'arr []' массиви жана k мааниси бар, эгерде биз анын көчүрмөлөрүн табышыбыз керек болсо, анда анда элементтерди сактоо үчүн hash set колдонулат, биз анын элементтерин кошобуз биздин хэштердеги массив бир-бирден, эгерде элемент хэш-топтомдо болсо, анда ал чыныгы болуп кайтып келип, циклди бузат, антпесе ал топтомго элементтерди киргизип, arr [ik] элементин топтомдон алып салат.

коду  

Берилген массивде бири-биринен k аралыкта кайталанган элементтер бар экендигин текшерүү үчүн C ++ коду

#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 коду

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) кайда "N" массивдеги элементтердин саны. Hash Setти колдонуу маселени сызыктуу убакытта чечүүгө мүмкүндүк берет. Хэш топтомун колдонуу натыйжалуу маалыматтарды издөө, жок кылуу жана киргизүү мүмкүнчүлүгүн өркүндөтөт.

ошондой эле
Берилген продукт менен жупташыңыз

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

O (k) кайда "K" бул терезедеги элементтердин саны, аларды караш керек.