ກວດເບິ່ງວ່າແຖວໃດ ໜຶ່ງ ມີສ່ວນປະກອບທີ່ຊ້ ຳ ກັນພາຍໃນໄລຍະ k ຈາກກັນແລະກັນ


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Amazon Avalara Citadel FreeCharge ແຮກເກີຣ SnapChat Snapdeal
Array Hash

ບັນຫາ“ ກວດເບິ່ງວ່າແຖວໃດ ໜຶ່ງ ມີສ່ວນປະກອບທີ່ຊ້ ຳ ກັນພາຍໃນໄລຍະຫ່າງໄກຈາກກັນແລະກັນ” ລະບຸວ່າພວກເຮົາຕ້ອງກວດເບິ່ງຊ້ ຳ ຊ້ອນໃນອາເລທີ່ບໍ່ມີສາຍໃນຂອບເຂດຂອງ 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

ຄໍາອະທິບາຍ

ພວກເຮົາມີສອງວິທີການເພື່ອແກ້ໄຂບັນຫານີ້. ສິ່ງທີ່ງ່າຍດາຍກວ່ານີ້ແມ່ນການແລ່ນສອງ loops ເຊິ່ງ loop ທຳ ອິດຈະເລືອກເອົາທຸກໆອົງປະກອບທີ່ເປັນອົງປະກອບເລີ່ມຕົ້ນ ສຳ ລັບ loop ທີສອງ 'Inner loop'. ຫລັງຈາກນັ້ນ, loop ທີສອງຈະປຽບທຽບອົງປະກອບທີ່ເລີ່ມຕົ້ນກັບອົງປະກອບທັງ ໝົດ ພາຍໃນຂອບເຂດ 'k'. ແຕ່ການແກ້ໄຂບັນຫານີ້ບໍ່ມີປະສິດຕິຜົນມັນຕ້ອງໃຊ້ເວລາສັບສົນກັບ O (k * n).

ແຕ່ພວກເຮົາມີວິທີການທີ່ມີປະສິດທິພາບອີກປະການ ໜຶ່ງ ເຊິ່ງສາມາດແກ້ໄຂບັນຫາໄດ້ O (n) ຄວາມສັບສົນທີ່ໃຊ້ເວລາເອີ້ນວ່າ ເຮື້ອຮັງ. ໃນວິທີການ hashing, ພວກເຮົາຈະຜ່ານສ່ວນປະກອບທັງ ໝົດ ຂອງອາເລແລະພວກເຮົາຈະກວດເບິ່ງວ່າອົງປະກອບມີຢູ່ໃນມັນຫຼືບໍ່ ຖ້າອົງປະກອບຢູ່ໃນນັ້ນພວກເຮົາຈະກັບຄືນ 'True.' ອີກອັນ ໜຶ່ງ ພວກເຮົາຈະເພີ່ມມັນໃສ່ hash ແລະເອົາອົງປະກອບ arr [ik] ອອກຈາກ hash ຖ້າ 'i' ໃຫຍ່ກວ່າຫຼືເທົ່າກັບ 'k'.

ສູດການຄິດໄລ່ເພື່ອກວດສອບວ່າອາເລທີ່ໃຫ້ມີສ່ວນປະກອບທີ່ຊ້ ຳ ກັນພາຍໃນ k ໄລຍະຫ່າງຈາກກັນແລະກັນ

  1. ຫນ້າທໍາອິດ, ສ້າງຫວ່າງເປົ່າ ທີ່ກໍານົດໄວ້ hash ໃນທີ່ພວກເຮົາຈະເກັບຮັກສາອົງປະກອບຂອງອາເລ.
  2. ລອກເອົາສ່ວນປະກອບທັງ ໝົດ ຂອງອາເລຈາກຊ້າຍຫາຂວາ.
  3. ກວດເບິ່ງວ່າອົງປະກອບມີຢູ່ໃນລັກສະນະຫລືບໍ່.
    • ຖ້າມັນຢູ່ໃນນັ້ນກໍ່ຈະກັບຄືນ "ຄວາມຈິງ."
    • ອື່ນເພີ່ມສ່ວນປະກອບນັ້ນເຂົ້າໃນເຮັກ.
  4. ຫລັງຈາກນັ້ນເອົາອົງປະກອບ arr [ik] ອອກຈາກ hash ຖ້າ 'ຂ້ອຍ' ໃຫຍ່ກວ່າຫລືເທົ່າກັບ 'k'.

 

ພວກເຮົາມີ array 'arr []' ທີ່ມີບາງອົງປະກອບໃນມັນແລະຄ່າ k ເຊິ່ງແມ່ນຊ່ວງທີ່ພວກເຮົາຕ້ອງຊອກຫາຊໍ້າກັນຖ້າມີອັນໃດ ໜຶ່ງ ກໍ່ຈະໃຊ້ຊຸດ hash ເພື່ອເກັບຮັກສາອົງປະກອບຕ່າງໆໄວ້ກ່ອນມັນພວກເຮົາຈະເພີ່ມອົງປະກອບຂອງ ອາເລຢູ່ໃນ hash ຂອງພວກເຮົາຕັ້ງແຕ່ລະອັນຖ້າວ່າອົງປະກອບຢູ່ໃນ hash ແລ້ວມັນກໍ່ຈະກັບມາເປັນຄວາມຈິງແລະ ທຳ ລາຍ loop ອີກຢ່າງ ໜຶ່ງ ມັນຈະສືບຕໍ່ໃສ່ອົງປະກອບຕ່າງໆໃນຊຸດແລະເອົາ Element [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

ການວິເຄາະຄວາມສັບສົນ

ຄວາມສັບສົນເວລາ

O (n) ບ່ອນທີ່ "n" ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ. ການໃຊ້ Hash Set ຊ່ວຍໃຫ້ການແກ້ໄຂບັນຫາເປັນໄລຍະເວລາ. ນັບຕັ້ງແຕ່ການນໍາໃຊ້ຊຸດ hash ຊ່ວຍເພີ່ມຄວາມສາມາດໃນການຄົ້ນຫາ, ລຶບແລະໃສ່ຂໍ້ມູນຢ່າງມີປະສິດຕິພາບ.

ຄວາມສັບສົນໃນອະວະກາດ

ຕົກ​ລົງ) ບ່ອນທີ່ “ k” ແມ່ນ ຈຳ ນວນຂອງສ່ວນປະກອບທີ່ຢູ່ໃນປ່ອງຢ້ຽມທີ່ຕ້ອງການເບິ່ງ.