ນັບ ຈຳ ນວນເລກຄີກໃນໄລຍະຫ່າງລະຫວ່າງ Leetcode Solution


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Microsoft
ຄະນິດສາດ

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

ໃນບັນຫານີ້, ພວກເຮົາໄດ້ຮັບສອງຕົວເລກທີ່ບໍ່ແມ່ນລົບຕໍ່ລະດັບຕໍ່າແລະສູງ. ພວກເຮົາຕ້ອງຊອກຫາຕົວເລກທີ່ຄີກທີ່ມີຢູ່ໃນຂອບເຂດໄລຍະຫ່າງ [ຕ່ ຳ, ສູງ].

ຍົກຕົວຢ່າງ

low = 3, high = 7
3

ຄໍາອະທິບາຍ:

ຕົວເລກທີ່ຄັກລະຫວ່າງ 3 ເຖິງ 7 ແມ່ນ [3, 5, 7].

low = 8, high = 10
1

ຄໍາອະທິບາຍ:

ຕົວເລກຄີກໃນລະຫວ່າງ 8 ແລະ 10 ແມ່ນ [9].

ວິທີການ

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

ມັນງ່າຍທີ່ສຸດທີ່ຈະຊອກຫາຕົວເລກຄີກທັງ ໝົດ ໃນຂອບເຂດໄລຍະທີ່ ກຳ ນົດໄວ້ດັ່ງທີ່ພວກເຮົາຮູ້ວ່າມີເກືອບເຄິ່ງ ໜຶ່ງ ແມ່ນແຕ່ເຄິ່ງ ໜຶ່ງ ແລະເລກຄີກໃນ ຈຳ ນວນໄລຍະຫ່າງ.
ແຕ່ພວກເຮົາຕ້ອງພິຈາລະນາເຂດແດນໄລຍະຫ່າງຢ່າງລະມັດລະວັງ. ດັ່ງນັ້ນສິ່ງທີ່ພວກເຮົາສາມາດເຮັດໄດ້ແມ່ນພວກເຮົາສາມາດສ້າງສູດ ສຳ ລັບການນັບ ຈຳ ນວນຂອງເລກຄີກໃນ ຈຳ ນວນ ທຳ ມະຊາດ ທຳ ອິດ. ໃຫ້ມັນຖືກນັບ [n]. ຫຼັງຈາກນັ້ນຕົວເລກຄີກລະຫວ່າງຕ່ ຳ ແລະສູງຈະເທົ່າກັບ:
count [ຕ່ ຳ, ສູງ] = ນັບ [ສູງ] - ນັບ [ຕ່ ຳ -1].

ນັບ ຈຳ ນວນເລກຄີກໃນໄລຍະຫ່າງລະຫວ່າງ Leetcode Solution

ຕອນນີ້ເອົາບາງຕົວຢ່າງ ສຳ ລັບການນັບ [i]:

ນັບ [1] = 1
ນັບ [2] = 1
ນັບ [3] = 2
ນັບ [4] = 2
ນັບ [5] = 3

ພວກເຮົາສາມາດຄິດໄລ່ມູນຄ່ານັ້ນ [n] = (n + 1) / 2
ເພາະສະນັ້ນຈຶ່ງນັບ [ຕ່ ຳ, ສູງ] = (ສູງ + 1) / 2 - ຕ່ ຳ / 2

ການປະຕິບັດ

ໂປແກຼມ C ++ (ວິທີການທີ່ບໍ່ຮູ້ຕົວ) ສຳ ລັບການນັບເລກຄີກໃນໄລຍະຫ່າງລະຫວ່າງ Leetcode Solution

#include <iostream>
using namespace std;

int countOdds(int low, int high) 
{
    int count=0;
    for(int i=low;i<=high;i++)
        if(i%2==1) count++;
        
    return count;
}

int main()
{
    int low=3,high=7;  
    cout<< countOdds(low, high) <<endl;
}
3

Java Program (ວິທີການ Naive) ສຳ ລັບການນັບເລກຄີກໃນໄລຍະຫ່າງລະຫວ່າງ Leetcode Solution

class CountOdd
{  
    public static int countOdds(int low, int high) 
    {
        int count=0;
        for(int i=low;i<=high;i++)
            if(i%2==1) count++;
        
        return count;
    }
    
    public static void main(String args[])
    {
        int low=3,high=7;
        System.out.println(countOdds(low, high));
    }
}
3

ໂຄງການ C ++ (ວິທີການທີ່ດີທີ່ສຸດ)

#include <iostream>
using namespace std;

int countOdds(int low, int high) 
{
   return (high + 1) / 2 - low / 2;       
}

int main()
{
    int low=3,high=7;  
    cout<< countOdds(low, high) <<endl;
}
3

Java Program (ວິທີການທີ່ດີທີ່ສຸດ)

class CountOdd
{  
    public static int countOdds(int low, int high) 
    {
        return (high + 1) / 2 - low / 2;   
    }
    
    public static void main(String args[])
    {
        int low=3,high=7;
        System.out.println(countOdds(low, high));
    }
}
3

ການວິເຄາະຄວາມສັບສົນ ສຳ ລັບ ຈຳ ນວນເລກຄີກໃນການແກ້ໄຂໄລຍະຫ່າງລະຫວ່າງ Leetcode

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

Traversing ສໍາລັບແຕ່ລະຕົວເລກຈະໃຊ້ເວລາ O (n) ຄວາມສັບສົນທີ່ໃຊ້ເວລາໃນຂະນະທີ່ ຄຳ ນວນ ans ໂດຍໃຊ້ສູດຕ້ອງໃຊ້ເວລາຄົງທີ່ O (1) ການປະຕິບັດ.

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

O (1): ບໍ່ມີພື້ນທີ່ພິເສດໃດໆທີ່ໃຊ້ໃນທັງສອງວິທີແກ້ໄຂຍົກເວັ້ນຕົວແປທີ່ຖືກໃຊ້ເພື່ອເກັບໂຕຕອບ.