algorithm - 查找范围内的整数个数

Question

我正在阅读算法导论第 3 版，我遇到了以下问题:假设我们给定了 0 到 k 范围内的 n 个整数，我们想找出这些整数中有多少在 [a,b ] 对于给定的整数 a 和 b。它有粗略的解决方案，但是它说通过对输入的预处理阶段，这个查询可以在 Θ(1) 时间内完成，而这个预处理阶段需要 O(n+k) 时间。我正在考虑对整数进行排序，但排序至少需要 O(nlogn) 时间，超过 O(n+k)。预处理阶段可以做什么？谢谢

Answer 1

由于数字在 [0,k] 范围内，您可以使用计数排序在 O(n+k) 时间内对它们进行排序。

一旦你有了计数，你就可以得到那个计数数组的前缀和，它会告诉你范围 [0, a] 中数字的数量。 O(k) 时间。

使用它，您可以在 O(1) 时间内通过取适当的差值来回答 [a,b] 的查询。