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

Question

我正在阅读第 3 版算法介绍，我遇到了以下问题：假设给定 n 个整数，范围为 0 到 k，我们想知道这些整数中有多少在 [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] 的查询。