LeetCode 1523. 在区间范围内统计奇数数目

约 2 分钟
文章信息 6 个分类 1 个标签
分类
LeetCode CodeTop 简单 未解决 1-2 字节
标签
数学

题目描述

✅ 1523. 在区间范围内统计奇数数目

image-20260929084852117

题意分析

给定非负整数 low <= high，统计闭区间 [low, high] 中奇数的数量，两个端点都要参与判断。

区间可能只包含一个数，也可能从零开始。范围较大，不需要逐个枚举，只需得到一个直接计数公式。

解法：前缀奇数计数公式

核心思路

[!blue]

从零开始，每两个连续整数组成一组，其中恰有一个奇数。若上界为偶数 2t，前缀里有 t 个奇数；若为奇数 2t+1，则有 t+1 个。统一写成整数除法 (high + 1) / 2。

要保留 [low, high]，应从这个前缀中去掉 [0, low - 1]。把前缀公式的上界换成 low - 1，奇数个数正好简化为 low / 2。

两者相减得到 (high + 1) / 2 - low / 2。当 low = 0 时，被去掉的前缀为空，对应数值也为零，因此无需实际计算负下标或额外分类。所有除法都作用于非负整数，截断与向下取整一致。

解题步骤

  1. 计算从零到右端点的奇数个数 (high + 1) / 2。
  2. 计算左端点之前的奇数个数 low / 2。
  3. 返回两者之差。

代码实现

class Solution {
    public int countOdds(int low, int high) {
        // (high+1)/2 是 [0, high] 内的奇数个数，low/2 是 [0, low-1] 内的奇数个数。
        // 整数除法自动向下取整，四种奇偶组合无需分支。
        return (high + 1) / 2 - low / 2;
    }
}

func countOdds(low int, high int) int {
    // (high+1)/2 是 [0, high] 内的奇数个数，low/2 是 [0, low-1] 内的奇数个数。
    // 整数除法自动向下取整，四种奇偶组合无需分支。
    return (high+1)/2 - low/2
}

复杂度分析

  • 时间复杂度：$O(1)$，只做固定次数的整数运算。
  • 空间复杂度：$O(1)$，不分配额外容器。

关键点总结

[!green]

  • 闭区间计数等于右端前缀减去左端之前的前缀。
  • 一条整数除法公式同时覆盖上下界的全部奇偶组合。
  • 左端为零时空前缀贡献为零，单点区间也自然成立。

易错点总结

[!yellow]

  • 使用 high / 2 统计包含右端的前缀，会在右端为奇数时少算它。
  • 减去包含 low 的前缀，会把合法左端点错误排除。
  • 只按区间长度除二后固定加一，无法同时处理两端的不同奇偶情况。

相似题目

题目 难度 关联与区别
303. 区域和检索 - 数组不可变 简单 同样把闭区间计数拆成两个前缀累计值之差，本题前缀奇数数量可以直接用整除公式求出。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/60589154
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！