ນັບ ຈຳ ນວນການສະ ໝັກ ໃຊ້ຕົວເລກທີ່ແຕກຕ່າງ


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Cisco Expedia Myntra ຫ້ອງທົດລອງ SAP Taxi4Sure
Array Hash ຊຸດຍ່ອຍ

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

ພາກທີ 1

ຖະແຫຼງການບັນຫາ

ພວກເຮົາໄດ້ຮັບການຕອບສະ ໜອງ ກັບການປະສົມປະສານ / ຕົວເລກຂອງຕົວເລກ. ພວກເຮົາຕ້ອງໄດ້ນັບ ຈຳ ນວນຊຸດຍ່ອຍທີ່ພວກເຮົາສາມາດມີໄດ້ເຖິງແມ່ນ ຈຳ ນວນທີ່ເປັນເອກະລັກ.

ຂໍໃຫ້ເຮົາຍົກຕົວຢ່າງຂະຫນາດນ້ອຍ:

ການປ້ອນຂໍ້ມູນ:

[1,2,5,6,3,2,1,1,8]

ຊຸດຍ່ອຍທີ່ເປັນໄປໄດ້:

[2,6]

[6,8]

[2,6,8]

ໝາຍ ເຫດ: ການສະ ໝັກ ສະມາຊິກທີ່ມີເລກດຽວກັນຈະບໍ່ຖືວ່າແຕກຕ່າງກັນ

ຂ້າພະເຈົ້າຂໍຍົກຕົວຢ່າງຄືກັນໂດຍການເນັ້ນ ຄຳ ຕອບ ໜຶ່ງ ຄຳ ຕອບທີ່ເປັນໄປໄດ້.

ນັບ ຈຳ ນວນການສະ ໝັກ ໃຊ້ຕົວເລກທີ່ແຕກຕ່າງ

ພາກທີ 2

ການວິເຄາະ

ມີຫລາຍໆວິທີໃນການຄົ້ນຫາສິ່ງທີ່ພວກເຮົາຕ້ອງການ. ທ ຜົນບັງຄັບໃຊ້ສັດ ຫນຶ່ງຈະໄດ້ຮັບການຊອກຫາຊຸດທັງຫມົດທີ່ເປັນໄປໄດ້ຫຼັງຈາກນັ້ນຊອກຫາສິ່ງທີ່ພໍໃຈກັບກົດລະບຽບຂອງພວກເຮົາ.

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

ພວກເຮົາມີສອງທາງເລືອກໃນທຸກໆຄັ້ງທີ່ພວກເຮົາພົບກັບເລກທີ່ຍັງຄ້າງຄາ

  • ມັນສາມາດເລືອກທີ່ຈະຢູ່ໃນຊຸດຍ່ອຍ
  • ມັນສາມາດເລືອກທີ່ຈະບໍ່ຢູ່ໃນຊຸດຍ່ອຍ

ດັ່ງນັ້ນ, ວຽກງານດຽວທີ່ພວກເຮົາມີກັບພວກເຮົາດຽວນີ້ແມ່ນ ກຳ ນົດວ່າ ຈຳ ນວນນັ້ນຈະເປັນເອກະລັກຫຼືບໍ່. (ຂໍຂອບໃຈກັບກົດລະບຽບທີ່ກ່າວມາຂ້າງເທິງ)

ໃຫ້ພວກເຮົາອອກຈາກຂະບວນການ:

  • ກ່ອນອື່ນ ໝົດ, ຮັກສາກ HashSet ເພື່ອເກັບຮັກສາ ຈຳ ນວນເລກທີ່ແມ່ນແຕ່ພວກເຮົາໄດ້ພົບ
  • ອັນທີສອງ, ດໍາເນີນການ loop
  • ກວດເບິ່ງວ່າມີ ຈຳ ນວນເລກໃດ
  • ຖ້າຫາກວ່າຕົວເລກແມ່ນແຕ່ພວກເຮົາເພີ່ມໃສ່ມັນ HashSet
  • HashSet ມີການຈັດ ລຳ ດັບດ້ວຍຕົນເອງເຊິ່ງຮັບປະກັນວ່າພວກເຮົາມີພຽງແຕ່ອົງປະກອບທີ່ເປັນເອກະລັກທີ່ເຂົ້າມາ
  • ຈາກນັ້ນພວກເຮົາຊອກຫາການນັບ ຈຳ ນວນຂອງອົງປະກອບຕ່າງໆໃນ HashSet
  • ຈຳ ນວນນີ້ສະແດງເຖິງ ຈຳ ນວນຂອງ ຈຳ ນວນທີ່ເປັນເອກະລັກທີ່ພວກເຮົາມີ
  • ພວກເຮົາສາມາດໃຊ້ການນັບນີ້ເພື່ອຊອກຫາ ຈຳ ນວນຊຸດຍ່ອຍ
  • ຈຳ ນວນຊຸດຍ່ອຍ = 2 ^ ນັບ -1

ຂະບວນການຂ້າງເທິງນີ້ສາມາດຖືກໃສ່ເປັນລະຫັດດັ່ງນີ້:

ລະຫັດ Java ສຳ ລັບການຈອງ ຈຳ ນວນນັບມີ ຈຳ ນວນທີ່ແຕກຕ່າງ

public class Main
{
    public static int evenSub(int arr[],int n)
    {
        HashSet<Integer>store=new HashSet<Integer>();
        for(int i=0;i<arr.length;i++)
        {
            if(arr[i]%2==0)
                store.add(arr[i]);
        }
        int p=store.size();
        return (int)(Math.pow(2,p)-1);
    }
    public static void main(String[] args)  
    { 
    int arr[] = {2, 1, 9, 2, 6, 5, 3}; 
    int n = arr.length; 
    System.out.println
        ("Number of subsets = "+ evenSub(arr, n)); 
    }
}
2, 1, 9, 2, 6, 5, 3
3

ລະຫັດ C ++ ສຳ ລັບການຈອງຍ່ອຍທີ່ມີ ຈຳ ນວນຕົວເລກທີ່ແຕກຕ່າງ

ເມື່ອພວກເຮົາປ່ຽນຈາກ Java ໄປເປັນ C ++, ພວກເຮົາຈະໃຊ້ Unordered Set ແທນທີ່ HashSet ແລະ flick ປະມານສອງສາມພາຫະນະເພື່ອໃຫ້ ເໝາະ ສົມກັບພວກເຮົາ.

int evenSub(int arr[],int n)
{
    unordered_set<int>store; 
    for(int i=0;i<n;i++)
    {
        if(arr[i]%2==0)
            store.insert(arr[i]);
    }
    int p=store.size();
    return (pow(2,p)-1);
}
int main() 
{
    int arr[] = {
4, 2, 1, 9, 2, 6, 5, 3
7

ການວິເຄາະຄວາມສັບສົນ ສຳ ລັບການຈອງຍ່ອຍທີ່ມີ ຈຳ ນວນຕົວເລກທີ່ແຕກຕ່າງ

ຄວາມສັບສົນເວລາ = O (n)

ຄວາມສັບສົນໃນອະວະກາດ = O (n)

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

  • ມັນແມ່ນ O (n) ດັ່ງທີ່ພວກເຮົາໄປຜ່ານແຖວ
  • ພວກເຮົາເບິ່ງເຂົ້າໄປໃນແຕ່ລະອົງປະກອບກ່ອນທີ່ຈະເພີ່ມເຂົ້າໃນຊຸດຍ່ອຍ

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

  • ມັນແມ່ນ O (n) ຄືກັນກັບໃນກໍລະນີທີ່ບໍ່ດີທີ່ສຸດທີ່ພວກເຮົາອາດຈະເກັບຮັກສາອາເລທັງ ໝົດ