นับเลขคี่ในโซลูชัน Leetcode ช่วงช่วงเวลา


ระดับความยาก สะดวกสบาย
ถามบ่อยใน ไมโครซอฟท์
คณิตศาสตร์

คำชี้แจงปัญหา

ในปัญหานี้เราได้รับจำนวนเต็มสองจำนวนที่ไม่เป็นลบต่ำและสูง เราต้องหาจำนวนคี่ในช่วงช่วงเวลาที่กำหนด [ต่ำ, สูง]

ตัวอย่าง

low = 3, high = 7
3

คำอธิบาย:

จำนวนคี่ระหว่าง 3 ถึง 7 คือ [3, 5, 7]

low = 8, high = 10
1

คำอธิบาย:

เลขคี่ระหว่าง 8 ถึง 10 คือ [9]

เข้าใกล้

วิธีหนึ่งในการค้นหาจำนวนรวมของจำนวนคี่ในช่วงช่วงเวลาที่กำหนดคือการสำรวจจากขอบซ้ายไปขวาของช่วงเวลาใน a ห่วง และเพิ่มตัวนับคี่สำหรับแต่ละจำนวนคี่ แต่นี่จะเป็นวิธีที่ง่อยมากสำหรับการนับจำนวนคี่ในช่วง สิ่งนี้จะใช้ความซับซ้อนของเวลาเชิงเส้นและเราไม่ต้องการให้เกิดปัญหาง่ายๆเช่นนี้

เป็นเรื่องง่ายมากที่จะหาจำนวนคี่ทั้งหมดในช่วงช่วงเวลาที่กำหนดเนื่องจากเรารู้ว่ามีเลขคี่เกือบครึ่งคู่และครึ่งหนึ่งในช่วงช่วงเวลา
แต่เราต้องพิจารณาขอบเขตช่วงเวลาอย่างรอบคอบ สิ่งที่เราทำได้คือเราสามารถสร้างสูตรสำหรับการนับจำนวนคี่ในจำนวนธรรมชาติ n ตัวแรกได้ ให้นับ [n] จากนั้นจำนวนคี่ระหว่างต่ำและสูงจะเท่ากับ:
count [ต่ำสูง] = นับ [สูง] - นับ [ต่ำ -1]

นับเลขคี่ในโซลูชัน Leetcode ช่วงช่วงเวลา

ตอนนี้ยกตัวอย่างการนับ [i]:

นับ [1] = 1
นับ [2] = 1
นับ [3] = 2
นับ [4] = 2
นับ [5] = 3

เราสามารถอนุมานได้ว่า count [n] = (n + 1) / 2
ดังนั้นนับ [ต่ำสูง] = (สูง + 1) / 2 - ต่ำ / 2

การดำเนินงาน

โปรแกรม C ++ (วิธีไร้เดียงสา) สำหรับการนับเลขคี่ในโซลูชัน Leetcode ช่วงช่วงเวลา

#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 (วิธีไร้เดียงสา) สำหรับการนับเลขคี่ในโซลูชัน Leetcode ช่วงช่วงเวลา

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 (แนวทางที่เหมาะสมที่สุด)

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 ช่วงช่วงเวลา

ความซับซ้อนของเวลา

การข้ามสำหรับแต่ละหมายเลขจะใช้เวลา O (n) ความซับซ้อนของเวลาในขณะที่คำนวณ ans โดยใช้สูตรจะใช้เวลาคงที่ O (1) เพื่อดำเนินการ

ความซับซ้อนของอวกาศ 

O (1): ไม่มีการใช้ช่องว่างเพิ่มเติมในโซลูชันทั้งสองยกเว้นตัวแปรที่ใช้ในการจัดเก็บ ans