找到一个范围内的整数

我正在阅读算法第3版的介绍，我遇到了以下情况：假设我们给出n个整数，范围为0到k，我们想知道这些整数有多少在给定整数a和b的范围[a，b]中。它具有暴力解决方案，但是它说，通过输入的预处理阶段，这个查询可以在Θ（1）时间内完成，并且这个处理阶段花费O（n + k）时间。我在考虑对整数进行排序，但排序至少需要O（nlogn）时间，超过O（n + k）。预处理阶段可以做些什么？谢谢找到一个范围内的整数

来源

2013-03-15 yrazlik

使用[哈希表]（http://stackoverflow.com/questions/5586200/algorithm-find-count-of-numbers-within-a-given-range）。它将是O（1）。 – 2013-03-15 10:07:53

算法书的作者？当引用一本书时，陈述作者。 – AlexWien 2013-03-15 10:12:11

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

一旦你有了计数，你可以获得该计数数组的前缀总和，它会告诉你在[0，a]范围内的数字个数。 O（k）时间。

使用它你可以在O（1）时间内取适当的差异来回答[a，b]的查询。

来源

2013-03-15 10:01:39 Knoothe

为什么要计数*排序*？只计数他们.. – harold 2013-03-15 10:03:55

谢谢，但不明白你的意思是“我们可以使用计数来对它们进行排序” – yrazlik 2013-03-15 10:04:22

@bigO：计算有多少零，那里有多少等等。你保持一个计数[0。 ..k]数组（初始化为0）。现在，每次获得数字j时，都会增加计数[j]。 – Knoothe 2013-03-15 10:14:07

找到一个范围内的整数

回答

相关问题