ບັນຈຸຊ້ ຳ ກັນ


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Adobe Amazon ຈາກຫນາກແອບເປີ
Array ແຮກ

ພວກເຮົາໄດ້ຮັບ array ແລະມັນອາດຈະມີສ່ວນປະກອບທີ່ຊ້ ຳ ກັນຫຼືອາດຈະບໍ່ມີ. ສະນັ້ນພວກເຮົາຕ້ອງກວດເບິ່ງວ່າມັນມີຊ້ ຳ ກັນບໍ່.

ຕົວຢ່າງ

ບັນຈຸຊ້ ຳ ກັນ

[1, 3, 5, 1]
true
[“apple”, “mango”, “orange”, “mango”]
true
[22.0, 4.5, 3.98, 45.6, 13.54]
false

ວິທີການ

ພວກເຮົາສາມາດກວດສອບແຖວໃນຫຼາຍວິທີເພື່ອກວດເບິ່ງວ່າມັນມີຊ້ ຳ ກັນຫຼືບໍ່. ວິທີການທົ່ວໄປທີ່ສຸດແມ່ນ“ ວິທີການໃຊ້ແບບ ກຳ ລັງສັດ”. ແຕ່ມັນມີຄວາມສັບສົນເວລາຂອງ O (n2) ແລະມັນແມ່ນສິ່ງທີ່ດີ ສຳ ລັບຈຸດປະສົງທາງວິຊາການເທົ່ານັ້ນ. ແຕ່ພວກເຮົາອີກວິທີ ໜຶ່ງ ເພື່ອແກ້ໄຂບັນຫາຂອງພວກເຮົາໃນເວລາທີ່ສັບສົນ ໜ້ອຍ ກວ່າ“ Hash set method” ຫລື“ Hash table method” ວິທີນີ້ມີປະສິດທິພາບຫຼາຍກ່ວາ“ ວິທີ Brute Force”. ວິທີການ Hash Set ໃຊ້ເວລາຄວາມສັບສົນຂອງ O (n).

ວິທີການຕັ້ງ Hash

ວິທີການນີ້ແມ່ນງ່າຍດາຍແລະມີປະສິດທິພາບກ່ວາວິທີອື່ນ. ສິ່ງທີ່ພວກເຮົາ ຈຳ ເປັນຕ້ອງຮູ້ວ່າຊຸດນັ້ນບໍ່ມີຊ້ ຳ ຊ້ອນກັນ. ນັ້ນ ໝາຍ ຄວາມວ່າຖ້າພວກເຮົາພະຍາຍາມເພີ່ມຄ່າຊ້ ຳ ທີ່ຖືກ ກຳ ນົດໄວ້ມັນຈະໃຫ້ຂໍ້ຜິດພາດ. ຖ້າພວກເຮົາໃຊ້ວິທີການນີ້ທັງ ໝົດ ທີ່ພວກເຮົາຕ້ອງເຮັດແມ່ນພຽງແຕ່ລອກເຂົ້າໄປໃນອົງປະກອບຂອງຂບວນ, ໃສ່ພວກມັນເຂົ້າໃນຊຸດ hash. ຈາກນັ້ນປຽບທຽບຂະ ໜາດ ຂອງຊຸດກັບອາເລ. ຖ້າມັນບໍ່ເທົ່າກັບທີ່ ກຳ ນົດໄວ້ແລ້ວອາເລປະກອບມີຊ້ ຳ ຊ້ອນກັນອີກບໍ່.

ລະບົບວິເຄາະ

  1. ຫນ້າທໍາອິດ, ພວກເຮົາສ້າງຫນ້າທີ່ທີ່ໃຊ້ເວລາອາເລເປັນການໂຕ້ຖຽງ.
  2. ຫລັງຈາກນັ້ນ, ໃນ ໜ້າ ທີ່ຂອງພວກເຮົາ, ພວກເຮົາສ້າງຊຸດທີ່ປະກອບດ້ວຍຄ່າທັງ ໝົດ ຂອງອາເລ.
  3. ຊຸດບໍ່ອະນຸຍາດໃຫ້ຊ້ ຳ ຊ້ອນ, ນັ້ນ ໝາຍ ຄວາມວ່າຖ້າອາເລປະກອບມີສິ່ງທີ່ຊ້ ຳ ກັນແລ້ວຂະ ໜາດ ຂອງມັນຈະແຕກຕ່າງກັບຂະ ໜາດ ຂອງຊຸດ.
  4. ສຸດທ້າຍ, ພວກເຮົາປຽບທຽບຂະ ໜາດ ຂອງທັງອາເລແລະຊຸດ. ຖ້າມີຄວາມແຕກຕ່າງກັນໃນຂະ ໜາດ ຂອງມັນແລ້ວອາເລປະກອບມີຊ້ ຳ ຊ້ອນອີກອົງປະກອບທັງ ໝົດ ແມ່ນແຕກຕ່າງ.

ຄໍາອະທິບາຍ

ໃນໂປແກຼມຂອງພວກເຮົາພວກເຮົາໃຊ້ຊຸດ hash ເພື່ອກວດເບິ່ງສິ່ງທີ່ຊ້ ຳ ຊ້ອນກັນກ່ອນອື່ນ ໝົດ, ພວກເຮົາຈະເຮັດ ໜ້າ ທີ່ກວດສອບ. ໃນທີ່ພວກເຮົາຈະເຮັດຊຸດຮັດແລະໃຫ້ຄ່າທັງ ໝົດ ຂອງອາເລ. ຫລັງຈາກຊຸດນັ້ນຈະເອົາຊ້ ຳ ຊ້ອນອອກມາຖ້າມັນປະກອບມີອັນໃດແລະຂະ ໜາດ ຂອງມັນຈະແຕກຕ່າງກັນຖ້າທຽບໃສ່ອາເລອື່ນມັນຈະບໍ່ມີຜົນຕໍ່ຂະ ໜາດ ຂອງຊຸດ.

ລະຫັດ C ++ ເພື່ອກວດເບິ່ງວ່າອາເລປະກອບມີສິ່ງທີ່ຊ້ ຳ ກັນ

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

bool contain_duplicate(int arr[], int n)
{
    unordered_set<int> myset;
    bool flag = 0;

    for (int i = 0; i < n; i++)
    {
        if (myset.find(arr[i]) == myset.end())
            myset.insert(arr[i]);

        else
        {
            flag = 1;
            break;
        }

    }
    return flag;
}
int main()
{
    int arr[] = {1, 5, 2, 4, 3, 7, 8, 9, 1};
    int n = sizeof(arr) / sizeof(int);

    cout<< boolalpha <<contain_duplicate(arr, n);
    return 0;
}
true

ລະຫັດ Java ເພື່ອກວດເບິ່ງວ່າ array ມີຊ້ ຳ ຊ້ອນ

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

class contain_duplicate
{

    public static boolean solution(Integer [] array)
    {

        Set<Integer> myset = new HashSet<> (Arrays.asList(array));

        if(array.length!=myset.size())
        {
            return true;
        }
        else
        {
            return false;
        }
    }

    public static void main(String[] args)
    {
        Integer [] array = { 1, 2, 3, 6, 4, 9, 8, 1};
        System.out.println(solution(array));

    }
}
true

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

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

O (n) ບ່ອນທີ່“ n” ແມ່ນຂະ ໜາດ ຂອງຂບວນ.

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

O (n) ເນື່ອງຈາກວ່າພື້ນທີ່ທີ່ໃຊ້ໂດຍຕາຕະລາງ hash ແມ່ນເສັ້ນຊື່ກັບ ຈຳ ນວນຂອງທາດໃນມັນ.