Description
給定兩個非負整數
low和high，回傳low到high（含）之間的奇數個數。
Example:
Input: low = 3, high = 7 Output: 3 (3, 5, 7)
Intuition#
核心思路：用數學公式直接計算，不需要遍歷——
[0, n]中有(n + 1) / 2個奇數。
- 暴力遍歷 O(n) 太慢，需要 O(1) 的數學公式
[0, n]中的奇數個數為(n + 1) / 2（整數除法）[low, high]中的奇數個數 =[0, high]的奇數數量 -[0, low-1]的奇數數量
Approaches#
1: 數學公式（前綴相減）#
- 概念: 利用
[0, n]中奇數個數的公式，用前綴差計算區間內的奇數個數 - 時間複雜度:
O(1) - 空間複雜度:
O(1)
class Solution {
fun countOdds(low: Int, high: Int): Int {
// [0, n] 中有 (n + 1) / 2 個奇數
// [low, high] = [0, high] - [0, low - 1]
return (high + 1) / 2 - low / 2
}
}⭐2: 直覺公式#
- 概念: 區間共
high - low + 1個數，一半是奇數一半是偶數；如果端點任一為奇數則多一個奇數 - 時間複雜度:
O(1) - 空間複雜度:
O(1)
class Solution {
fun countOdds(low: Int, high: Int): Int {
val count = high - low + 1
return if (low % 2 == 1 || high % 2 == 1) {
count / 2 + 1
} else {
count / 2
}
}
}🔑 Takeaways#
- Pattern: 區間計數問題用前綴差公式 O(1) 求解
- 關鍵技巧:
(high + 1) / 2 - low / 2是最簡潔的公式，利用整數除法的截斷特性