Easy

题目描述

给定两个非负整数 low 和 high。返回 low 和 high 之间（包括 low 和 high）奇数的数目。

示例 1：

输入：low = 3, high = 7
输出：3
解释：3 到 7 之间的奇数有 [3,5,7]。

示例 2：

输入：low = 8, high = 10
输出：1
解释：8 到 10 之间的奇数有 [9]。

提示：

  • 0 <= low <= high <= 10^9
  • 如果范围 (high - low + 1) 是偶数，那么这个范围内偶数和奇数的个数相等。
  • 如果范围 (high - low + 1) 是奇数，解决方案将取决于 high 和 low 的奇偶性。

解题思路

这道题有两种主要解法：

方法一：数学公式法（推荐） 核心思想是利用数学性质直接计算。在任意连续的整数区间内，奇数和偶数的分布是相对均匀的。

  • 区间总长度为 high - low + 1
  • 如果总长度是偶数，奇数个数 = 总长度 / 2
  • 如果总长度是奇数，需要根据起始点的奇偶性判断：
    • 若 low 是奇数，奇数个数 = (总长度 + 1) / 2
    • 若 low 是偶数，奇数个数 = 总长度 / 2

方法二：前缀和思想 计算 [0, high] 范围内的奇数个数减去 [0, low-1] 范围内的奇数个数。对于区间 [0, n]，奇数个数为 (n + 1) / 2（整数除法）。

两种方法时间复杂度都是 O(1)，推荐使用更直观的数学公式法。

代码实现

class Solution {
public:
    int countOdds(int low, int high) {
        int length = high - low + 1;
        if (length % 2 == 0) {
            return length / 2;
        } else {
            return low % 2 == 1 ? (length + 1) / 2 : length / 2;
        }
    }
};

class Solution:
    def countOdds(self, low: int, high: int) -> int:
        length = high - low + 1
        if length % 2 == 0:
            return length // 2
        else:
            return (length + 1) // 2 if low % 2 == 1 else length // 2

public class Solution {
    public int CountOdds(int low, int high) {
        int length = high - low + 1;
        if (length % 2 == 0) {
            return length / 2;
        } else {
            return low % 2 == 1 ? (length + 1) / 2 : length / 2;
        }
    }
}

/**
 * @param {number} low
 * @param {number} high
 * @return {number}
 */
var countOdds = function(low, high) {
    return Math.floor((high + 1) / 2) - Math.floor(low / 2);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(1)
空间复杂度O(1)

相关题目